TR15-014 Authors: Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

Publication: 30th January 2015 10:38

Downloads: 1643

Keywords:

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 $\lim_{n,R\to\infty} R/R'$ positive.

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)}$.