# Theory Seminar: Communication over Highly Connected Noisy Networks

Speaker:
Ran Gelles (Princeton University)
Date:
Wednesday, 21.1.2015, 12:30
Place:
Taub 401

We consider the task of multiparty computation performed over networks in the presence of random noise. Given an \$n\$-party protocol that takes \$R\$ rounds assuming noiseless communication, the goal is to find a coding scheme that takes \$R'\$ rounds and computes the same function with high probability even when the communication is noisy, while maintaining a constant asymptotical rate, i.e. while keeping \$R/R'\$ positive as \$n\$ and \$R\$ increase.

Rajagopalan and Schulman (STOC '94) were the first to consider this question, and provided a coding scheme with rate \$O(1/\log (d+1))\$, where \$d\$ is the maximal degree of connectivity in the network. While that scheme provides a constant rate coding for many practical situations, in the worst case, e.g., when the network is a complete graph, the rate is \$O(1/\log n)\$, which tends to 0 as \$n\$ tends to infinity. We revisit this question and provide an efficient coding scheme with a constant rate for the interesting case of fully connected networks. We furthermore extend the result and show that if the network has mixing time \$m\$, then there exists an efficient coding scheme with rate \$O(1/m^3\log m)\$. This implies a constant rate coding scheme for any \$n\$-party protocol over a network with a constant mixing time, and in particular for random graphs with \$n\$ vertices and degrees \$n^{\Omega(1)}\$.

Joint work with Noga Alon, Mark Braverman, Klim Efremenko and Bernhard Haeupler.

Back to the index of events