On the Number of Binary-Minded Individuals Required To Compute $\sqrt\frac12$ - Archive ouverte HAL Access content directly
Journal Articles Theoretical Computer Science Year : 2011

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

(1) , (1, 2, 3, 4)
1
2
3
4
Olivier Bournez
Guillaume Aupy

#### 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.

### Dates and versions

hal-00760928 , version 1 (04-12-2012)

### Identifiers

• HAL Id : hal-00760928 , version 1
• DOI :

### Cite

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

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

230 View