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

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

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)

Cites Work

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

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)