TY - GEN

T1 - Interactive coding over the noisy broadcast channel

AU - Efremenko, Klim

AU - Kol, Gillat

AU - Saxena, Raghuvansh

PY - 2018/6/20

Y1 - 2018/6/20

N2 - 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 log log n) 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.

AB - 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 log log n) 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.

KW - Communication complexity

KW - Interactive coding

KW - Wireless broadcast

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

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

U2 - 10.1145/3188745.3188884

DO - 10.1145/3188745.3188884

M3 - Conference contribution

AN - SCOPUS:85049893433

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 890

EP - 901

BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Henzinger, Monika

A2 - Kempe, David

A2 - Diakonikolas, Ilias

PB - Association for Computing Machinery

T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018

Y2 - 25 June 2018 through 29 June 2018

ER -