streaming algorithm developers

Abstract: Determining the communication complexity of graph connectivity has been one of the longest standing open problems in communication complexity since the seminal work of Babai, Frankl, and Simon [FOCS'86]. A simple protocol transmits a spanning forest using $O(N\log N)$ communication on $N$-vertex graphs. While this was shown optimal for deterministic protocols by Hajnal, Maass, and Turán [STOC'88], the optimal nondeterministic and randomized complexities have remained unresolved for decades. We settle the nondeterministic communication complexity of graph connectivity by proving an optimal $Ω(N\log N)$ lower bound. The best prior bound was $Ω(N\log\log N)$ due to Raz and Spieker [Combinatorica'95]. Our bound is shown by upper bounding the maximum size of $1$-monochromatic rectangles. Generalizing our techniques to weighted, almost $1$-monochromatic rectangles yields an $Ω(N \cdot \log(\min(1/\varepsilon,N)))$ lower bound for randomized protocols with error probability $\varepsilon$. In particular, this bound is optimal for any polynomially small $\varepsilon$. For constant error probability, we also prove that any $r$-round protocol requires $Ω(N/r \cdot \log N)$ communication, which is optimal for every constant $r$. Previously, optimal $Ω(N\log N)$ lower bounds for graph connectivity were known only for $1$-round [Sun, Woodruff; APPROX/RANDOM'15] and $2$-round protocols [Radhakrishnan, Reddy, Venkat; ITCS'26]. Our proof introduces a new communication problem which can be viewed as a composition of inner product and pointer chasing problems. Our lower bounds can be extended to other fundamental graph properties, and also imply optimality of known query and streaming algorithms for related problems.

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.