Lower Bounds for Leader Election and Collective Coin Flipping, Revisited
Mohit Gurumukhani (Cornell)
Monday, May 12th 2025, 2-3pm
Abstract:
We study the tasks of collective coin flipping and leader election in the full-information model where despite decades of study, key gaps remain in our understanding of the trade-offs between round complexity, communication per player in each round, and adversarial resilience.
We prove new lower bounds for coin flipping protocols, which also imply lower bounds for leader election protocols. Specifically, we show that any k-round coin flipping protocol, where each of l players sends 1 bit per round, can be biased by O(l / log^{(k)}(l)) bad players, strengthening the previous best lower bounds [RSZ, SICOMP 2002] which ruled out protocols resilient to adversaries controlling O(l / log^{(2k-1)}(l)) bad players. As a consequence, we establish that any protocol tolerating a linear fraction of corrupt players, while restricting player messages to 1 bit per round, must run for at least log^*(l) - O(1) rounds, improving on the prior best lower bound of 0.5 log^*(l) - log^*(log^*(l)). This also matches the number of rounds, log^*(l), taken by the current best coin flipping protocols from [RZ, JCSS 2001], [F, FOCS 1999] given the additional freedom that players can send unlimited bits per round. We additionally show that the protocols from [RZ, JCSS 2001], [F, FOCS 1999] are almost optimal in terms of round complexity and communication per player in a round.
Complementing our lower bound results, we give improved constant-round coin flipping protocols in the setting that each player can send 1 bit per round. For example, in the case of two rounds, our protocol can handle O(l / (log(l))(log(log(l))^2) sized coalition of bad players; this is better than the best one-round protocol (also called a resilient function) by [AL, Combinatorica 1993] in this setting, which can only handle O(l / (log(l))^2) sized coalition of bad players.
Joint work with Eshan Chattopadhyay, Noam Ringach, Rocco Servedio.