## Abstract

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 asymptotic rate, i.e., while keeping lim inf _{n} _{,} _{R} _{→} _{∞}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 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 a (d-regular) 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 d-regular network with a constant mixing time, and in particular for random graphs with n vertices and degrees n^{Ω} ^{(} ^{1} ^{)}.

Original language | English (US) |
---|---|

Pages (from-to) | 505-515 |

Number of pages | 11 |

Journal | Distributed Computing |

Volume | 32 |

Issue number | 6 |

DOIs | |

State | Published - Dec 1 2019 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Computational Theory and Mathematics

## Keywords

- Coding theory
- Computation with noise
- Interactive coding
- Random noise