Interactive coding over the noisy broadcast channel

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?

Authors

• Klim Efremenko
• Gillat Kol
• Raghuvansh R. Saxena

Keywords

• Wireless broadcast
• Communication complexity
• Interactive coding