ECCC-Report TR15-197https://eccc.weizmann.ac.il/report/2015/197Comments and Revisions published for TR15-197en-usMon, 07 Dec 2015 07:24:57 +0200
Paper TR15-197
| Constant-rate coding for multiparty interactive communication is impossible |
Mark Braverman,
Klim Efremenko,
Ran Gelles,
Bernhard Haeupler
https://eccc.weizmann.ac.il/report/2015/197We 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.Mon, 07 Dec 2015 07:24:57 +0200https://eccc.weizmann.ac.il/report/2015/197