Interactive coding over the noisy broadcast channel
Interactive coding over the noisy broadcast channel
复制标题
在嘈杂的广播信道上进行交互式编码
DOI：
10.1145/3188745.3188884
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Raghuvansh R. Saxena
中科院分区：
文献类型：
--
作者：
K. Efremenko;Gillat Kol;Raghuvansh R. Saxena
一组n个播放器，每个持有一个私人输入比特，通过嘈杂的广播信道进行通信。他们的共同目标是让所有的参与者学习所有的输入。在每一轮中，一个玩家向所有其他玩家广播一个比特，每个玩家接收的比特以固定的恒定概率被翻转(对于每个接收者独立)。需要多少发子弹？这个问题最早是由El Gamal在1984年提出的。1988年，Gallager给出了一个优雅的抗噪声协议，只需要O(Nlogn)轮。2005年，戈亚尔、金德勒和萨克斯的一篇开创性论文解决了这个问题，证明了加拉格尔的协议本质上是最优的。我们重新讨论了上面的噪声广播问题，并证明了O(N)轮就足够了。这是可能的，因为放宽了前人工作所假定的模型。我们不再要求每一轮只有一个玩家进行转播，而是允许任意数量的玩家进行转播。然而，如果不是恰好有一个玩家选择广播，则每个其他玩家都得到相反的选择比特。我们推广了上述结果，开启了噪声广播信道下交互编码的研究。我们证明了任何在无噪声广播信道上工作的交互协议都可以在我们的受限噪声广播模型上进行模拟，并且通信不断地爆炸。我们的结果也证明了现代交互编码技术可以帮助我们在经典问题上取得进展。
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.
通过高度连接的嘈杂网络进行可靠通信
影响因子：
1.3
作者：
Alon, Noga;Braverman, Mark;Efremenko, Klim;Gelles, Ran;Haeupler, Bernhard
通讯作者：
Haeupler, Bernhard