On the number of binary-minded individuals required to compute 12

DOI10.1016/J.TCS.2011.01.003zbMATH Open1216.68107OpenAlexW77532971MaRDI QIDQ533865FDOQ533865

Authors Guillaume Aupy, Olivier Bournez 

Publication date 10 May 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.01.003

zbMATH Keywords

complexitypopulation protocolsprobabilistic analysiscomputabilityprobabilistic systemsconvergence proof

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Stochastic ordinary differential equations (aspects of stochastic analysis) (60H10)

Recommendations

• Space-optimal proportion consensus with population protocols
• Brief announcement: Population protocols for leader election and exact majority with \(O(\log^{2} n)\) states and \(O(\log^{2}n)\) convergence time
• Computing with Large Populations Using Interactions
• Brief Announcement
• scientific article; zbMATH DE number 7204593

Cites work

• Computation in networks of passively mobile finite-state sensors
• On the convergence of population protocols when population goes to infinity
• Probability and Computing
• Stably computable predicates are semilinear

Cited in

(1)

• On the algebraic numbers computable by some generalized Ehrenfest urns

This page was built for publication: On the number of binary-minded individuals required to compute \(\sqrt {\frac 12}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q533865)