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

CREATOREshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Rocco A. Servedio
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE178 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-01856

Browse the full library · About the Tower of Babel