TY - GEN

T1 - Tight Bounds for General Computation in Noisy Broadcast Networks

AU - Efremenko, Klim

AU - Kol, Gillat

AU - Paramonov, Dmitry

AU - Saxena, Raghuvansh R.

N1 - Publisher Copyright:
© 2022 IEEE.

PY - 2022

Y1 - 2022

N2 - 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 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 Ω(log T) overhead (which always suffices)? We answer both the above questions in the negative: We give a simulation scheme with an tildeO(√{ log T}) overhead for every protocol and channel alphabet. We also prove an (almost) matching lower bound of Ω(√{ log T}) on the overhead required to simulate the pointer chasing protocol with T = n and polynomial alphabet.

AB - 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 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 Ω(log T) overhead (which always suffices)? We answer both the above questions in the negative: We give a simulation scheme with an tildeO(√{ log T}) overhead for every protocol and channel alphabet. We also prove an (almost) matching lower bound of Ω(√{ log T}) on the overhead required to simulate the pointer chasing protocol with T = n and polynomial alphabet.

UR - http://www.scopus.com/inward/record.url?scp=85127151240&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85127151240&partnerID=8YFLogxK

U2 - 10.1109/FOCS52979.2021.00068

DO - 10.1109/FOCS52979.2021.00068

M3 - Conference contribution

AN - SCOPUS:85127151240

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 634

EP - 645

BT - Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021

PB - IEEE Computer Society

T2 - 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021

Y2 - 7 February 2022 through 10 February 2022

ER -