HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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

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
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

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 : Monday, May 16, 2022 - 4:46:02 PM
Long-term archiving on: : Wednesday, March 6, 2013 - 4:50:12 PM

File

taillepopulation.pdf
Files produced by the author(s)

Identifiers

Collections

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⟩

Share

Metrics

Record views

228

Files downloads

252