FR2.R9.3

Computation in Server-Assisted Noisy Networks

Manuj Mukherjee, Indraprastha Institute of Information Technology Delhi, India; Ran Gelles, Bar Ilan University, Israel

Session:
Complexity and Computation Theory 2

Track:
21: Other topics

Location:
Lamda

Presentation Time:
Fri, 12 Jul, 12:10 - 12:30

Session Chair:
Manuj Mukherjee, Manuj Mukherjee
Abstract
We analyze resilient protocols over noisy networks, focusing on the interesting setting where $n$ computing parties (clients) are supported by a set of $k$ assisting servers. All communication links suffer from random noise, and the goal is to design noise-resilient computations with low round-complexity compared to the noiseless case. We give tight bounds for the case where a constant number of servers is present. We show that $\Theta(\log n)$ rounds are necessary and sufficient to compute any non-constant function of the clients' inputs, with error probability tending to~0. We further show a lower bound of $\Omega(\log n/k)$ rounds, for networks with $k< O(\log n)$ servers. This lower bound suggests that additional assisting servers could help reducing the overall round complexity.
Resources