Improved Bounds for Coin Flipping, Leader Election, and Random Selection
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Rocco A. Servedio · 2025
Read Improved Bounds for Coin Flipping, Leader Election, and Random Selection by Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Rocco A. Servedio (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-01856.txt.
Introduction
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, and Rocco Servedio prove new bounds, in a 2025 paper, for three basic tasks in shared computing. The tasks are flipping a shared coin, picking a leader, and picking random bits. All must work even when some players cheat. The team works in a model where each player sends one bit per round and all can see all past bits.
They show how many bad players can sway a coin flip in a set number of rounds. The bound beats the best past bound from 2002 for both coin flips and leader choice. It also shows that any plan that stands up to a fixed share of cheats needs a set floor of rounds. The team then gives a one-round random pick plan that is the best of its kind.
Catalog record
| CREATOR | Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Rocco A. Servedio |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 178 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-01856