Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-160 | 15th November 2021 21:38

Tight Bounds for General Computation in Noisy Broadcast Networks


Authors: Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
Publication: 15th November 2021 23:18
Downloads: 257


Let $\Pi$ be a protocol over the $n$-party broadcast channel, where in each round, a pre-specified party broadcasts a symbol to all other parties. We wish to design a scheme that takes such a protocol $\Pi$ as input and outputs a noise resilient protocol $\Pi'$ that simulates $\Pi$ over the noisy broadcast channel, where each received symbol is flipped with a fixed constant probability, independently. What is the minimum overhead in the number of rounds that is incurred by any such simulation scheme?

A classical result by Gallager from the 80's shows that non-interactive $T$-round protocols, where the bit communicated in every round is independent of the communication history, can be converted to noise resilient ones with only an $\mathcal{O}(\log \log T)$ multiplicative overhead in the number of rounds. Can the same be proved for any protocol? Or, are there protocols whose simulation requires an $\Omega(\log T)$ overhead (which always suffices)?

We answer both the above questions in the negative: We give a simulation scheme with an $\tilde{O}(\sqrt{\log T})$ overhead for every protocol and channel alphabet. We also prove an (almost) matching lower bound of $\Omega(\sqrt{\log T})$ on the overhead required to simulate the pointer chasing protocol with $T=n$ and polynomial alphabet.

ISSN 1433-8092 | Imprint