期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Let 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 as input and outputs a noise resilient protocol that simulates 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 (loglogT) multiplicative overhead in the number of rounds. Can the same be proved for any protocol? Or, are there protocols whose simulation requires an (logT) overhead (which always suffices)? We answer both the above questions in the negative: We give a simulation scheme with an O(logT) overhead for every protocol and channel alphabet. We also prove an (almost) matching lower bound of (logT) on the overhead required to simulate the pointer chasing protocol with T=n and polynomial alphabet.
