# On the Number of Binary-Minded Individuals Required To Compute $\sqrt\frac12$

3 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We recently obtained partial results on the computational power of population protocols when population is assumed to be huge. We studied in particular a particular protocol that we proved to converge towards $\sqrt{\frac12}$, using weak-convergence methods for stochastic processes. In this note, we prove that this is possible to compute $\sqrt{\frac12}$ with precision $\epsilon>0$ in a time polynomial in $\frac1\epsilon$ using a number of agents polynomial in $\frac1\epsilon$, with individuals that can have only two states. This is established through a general result on approximation of stochastic differential equations by a stochastic Euler like discretization algorithm, of general interest.
Document type :
Journal articles

Cited literature [7 references]

https://hal-polytechnique.archives-ouvertes.fr/hal-00760928
Contributor : Olivier Bournez Connect in order to contact the contributor
Submitted on : Tuesday, December 4, 2012 - 3:40:16 PM
Last modification on : Saturday, September 11, 2021 - 3:17:40 AM
Long-term archiving on: : Wednesday, March 6, 2013 - 4:50:12 PM

### File

taillepopulation.pdf
Files produced by the author(s)

### Citation

Olivier Bournez, Guillaume Aupy. On the Number of Binary-Minded Individuals Required To Compute $\sqrt\frac12$. Theoretical Computer Science, Elsevier, 2011, 411 (22), pp.2262--2267. ⟨10.1016/j.tcs.2011.01.003⟩. ⟨hal-00760928⟩

Record views