Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-014 | 18th January 2015 10:02

Reliable Communication over Highly Connected Noisy Networks



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

ISSN 1433-8092 | Imprint