Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-197 | 7th December 2015 01:37

Constant-rate coding for multiparty interactive communication is impossible


Authors: Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler
Publication: 7th December 2015 07:24
Downloads: 1733


We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability $\epsilon$. We analyze the minimal overhead that must be added by the coding scheme in order to succeed in performing the computation despite the noise.

Our main result is a lower bound on the communication of any noise-resilient protocol over a star network with $n$-parties. Specifically, we show a task that can be solved by communicating $Tn$ bits over the noise-free network, but for which any protocol with success probability of $1-o(1)$ must communicate at least $\Omega(Tn \frac{\log n}{\log\log n})$ bits when the channels are noisy. By a 1994 result of Rajagopalan and Schulman, the slowdown we prove is the highest one can obtain on any topology, up to a $\log \log n$ factor.

We complete our lower bound with a matching coding scheme that achieves the same overhead; thus, the capacity of star networks is $\Theta(\log\log n /\log n)$. Our bounds prove that, despite several previous coding schemes with rate $\Omega(1)$ for certain topologies, no coding scheme with constant rate $\Omega(1)$ exists for arbitrary $n$-party noisy networks.

ISSN 1433-8092 | Imprint