arXiv preprint ·
The Communication Complexity of the Coin Problem
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Online Batching with Lookahead: Adversarial Limits and Stochastic Gains
Improved Combinatorial Auctions with and without Samples
QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Stochastic Weighted Caching with Per-Request Predictions
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.