Communication bounds found for deciding more heads or tails
The Communication Complexity of the Coin Problem
Data Structures and Algorithms
Summary
This paper studies how much two people, each holding a number of random coins, need to communicate to tell if there are more heads or tails overall. While it’s easy to send exact counts using about log(n) bits, the authors show this is not the best way in one-way communication between two players. They prove that far fewer bits, around log log n, are actually needed for a constant error chance, and this is nearly optimal. They also provide new lower bounds and communication methods using simpler arguments than before, and extend the results to multiple rounds of communication.
What this means in practice
- •For distributed system designers: Optimize communication protocols determining majority outcomes from distributed random inputs with limited messaging.
- •For streaming algorithm developers: Bound communication costs when estimating majority elements in data streams with communication constraints.
A theory result. No direct application yet.
Authors
Adithya Diddapur, Pachara Sawettamalya
Abstract
We study the two-player communication complexity of the \textsf{Coin} problem. Here, two players, denoted Alice and Bob, are given up to $n$ individual i.i.d. random coins, and asked to output whether there are more heads or tails. An immediate approach is for Alice to send Bob her exact numbers of heads and tails, yielding a deterministic protocol with one-way communication cost $O(\log n)$ bits. Indeed, this is provably optimal in the related multi-player and streaming settings [Braverman, Garg, Woodruff, FOCS'20]. Our contribution is to show that this is not the right answer in the one-way two-player setting. Instead, we prove a $Ω(\log\log n)$ bit lower bound for the constant error-rate regime, and a $Ω(\log(1/δ))$ bit lower bound for arbitrarily small error rates, $δ\geq n^{-0.1}$. We also complement these with a tight one-way protocol using $O(\log\log n + \log(1/δ))$ bits of communication. Unlike the previous works, our lower bounds avoid intricate direct information-theoretic arguments. Instead, our $Ω(\log(1/δ))$ bound is via a standard fooling-set style argument, whilst our $Ω(\log\log n)$ bound is via a novel yet simple reduction from the \textsf{Gap-Greater-Than} problem. This reduction is our main technical contribution, and can be seen as loosely inspired by the \emph{Robust Communication Complexity} arguments of [Chakrabarti, Cormode, McGregor, STOC'08]. Finally, we also show that our constant-error lower bound and protocol can be adapted to the multi-round setting: up to polynomial factors in $r$, the $r$-round communication complexity of the coin problem is $Θ\left((\log\log n)^{1/r}\right)$ bits.