ECCC-Report TR15-014https://eccc.weizmann.ac.il/report/2015/014Comments and Revisions published for TR15-014en-usFri, 30 Jan 2015 10:38:49 +0200
Paper TR15-014
| Reliable Communication over Highly Connected Noisy Networks |
Ran Gelles,
Noga Alon,
Mark Braverman,
Klim Efremenko,
Bernhard Haeupler
https://eccc.weizmann.ac.il/report/2015/014We 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)}$.Fri, 30 Jan 2015 10:38:49 +0200https://eccc.weizmann.ac.il/report/2015/014