# 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.