Skip to main content

Interactive coding over the noisy broadcast channel

Author(s): Efremenko, Klim; Kol, Gillat; Saxena, Raghuvansh

To refer to this page use:
Abstract: A set of n players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit received by each player is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed? This problem was first suggested by El Gamal in 1984. In 1988, Gallager gave an elegant noise-resistant protocol requiring only O(n loglogn) rounds. The problem got resolved in 2005 by a seminal paper of Goyal, Kindler, and Saks, proving that Gallager’s protocol is essentially optimal. We revisit the above noisy broadcast problem and show that O(n) rounds suffice. This is possible due to a relaxation of the model assumed by the previous works. We no longer demand that exactly one player broadcasts in every round, but rather allow any number of players to broadcast. However, if it is not the case that exactly one player chooses to broadcast, each of the other players gets an adversely chosen bit. We generalized the above result and initiate the study of interactive coding over the noisy broadcast channel. We show that any interactive protocol that works over the noiseless broadcast channel can be simulated over our restrictive noisy broadcast model with constant blowup of the communication. Our results also establish that modern techniques for interactive coding can help us make progress on the classical problems.
Publication Date: Jun-2018
Citation: Efremenko, Klim, Gillat Kol, and Raghuvansh Saxena. "Interactive coding over the noisy broadcast channel." In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (2018): pp. 507-520. doi: 10.1145/3188745.3188884
DOI: 10.1145/3188745.3188884
Pages: 507 - 520
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings of the Annual ACM Symposium on Theory of Computing
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.