Tight Bounds for General Computation in Noisy Broadcast Networks
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena · 2022
Let II 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 II as input and outputs a noise resilient protocol II’ that simulates II 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$\mathrm{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.