The Taub Faculty of Computer Science Events and Talks

In this talk, we will consider coding schemes for multi-party interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability ε. 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 in T rounds over the noise-free network, but for which any protocol with a success probability of 1 − o(1) requires, at least, Ω(T log n / loglog n) rounds 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 Θ(log log n / log n). Our bounds prove that, despite several previous coding schemes with rate Ω(1) for certain topologies, no coding scheme with constant rate Ω(1) exists for arbitrary n-party noisy networks.

Joint work with Mark Braverman, Ran Gelles, Bernhard Haeupler