Date: January 26, 2026
Time: 3:45-5 p.m.
Location: Computing and Information Science Building, Room 450 or Click here to attend via Zoom
Speaker: Mohit Gurumukhani
Abstract: Two fundamental and widely studied tasks in fault-tolerant distributed computing are collective coin flipping - where processors agree on a common random bit - and leader election - where processors designate a leader amongst themselves. We generalize these tasks and initiate the study of collectively flipping many coins where processors want to agree on many common random bits. We study this problem in the full-information model with one round where each player sends one bit. Here, processors communicate via a single broadcast channel, have access to private randomness, and face a computationally unbounded adversary that controls some of the processors.
We obtain a protocol resilient to L / log(L)^2 bad processors that outputs log(L)^2 / log(log(L))^2 uniform random bits. Our resilience parameter matches that of the best coin flipping protocol in this setting by Ajtai and Linial, which only outputs one bit. We also obtain an almost matching lower bound: we show that any protocol outputting these many uniform random bits can be corrupted using L log(log(L))^2 / log(L)^2 bad processors, leaving only a poly(log(log(L))) multiplicative gap. To obtain our lower bound, we introduce and study multi-output influence, a natural extension of the notion of influence of boolean functions to the multi-output setting.
Based on joint work with Eshan Chattopadhyay, Noam Ringach, and Rocco Servedio: https://arxiv.org/abs/2504.01856.
Bio: Mohit Gurumukhani is a PhD student at Cornell University advised by Eshan Chattopadhyay. His research interests include complexity theory, pseudorandomness, analysis of boolean functions, and circuit complexity.