Toward Coding for Maximum Errors in Interactive Communication
Toward Coding for Maximum Errors in Interactive Communication
复制标题
交互式通信中针对最大错误的编码
DOI：
--
复制
发表时间：
2011
影响因子：
2.5
通讯作者：
Anup Rao
中科院分区：
文献类型：
--
作者：
M. Braverman;Anup Rao
我们表明，它是可能的编码任何通信协议之间的两方，使协议成功，即使（1/4 - 1/4）的一部分，由各方发送的所有符号被损坏的adversarially，在增加的通信协议中的一个乘法因子，只依赖于1/4，使用一个字母表的大小只取决于1/4。这改进了Schulman的早期结果，Schulman展示了如何在错误分数以1/240为界时进行恢复。我们还展示了如何模拟一个任意的协议与协议使用的二进制字母表，一个恒定的因素增加的通信，并容忍1/8的错误。
We show that it is possible to encode any communication protocol between two parties so that the protocol succeeds even if a (1/4 - ϵ) fraction of all symbols transmitted by the parties are corrupted adversarially, at a cost of increasing the communication in the protocol by a multiplicative factor that depends only on ϵ, using an alphabet whose size depends only on ϵ. This improves on an earlier result of Schulman, who showed how to recover when the fraction of errors is bounded by 1/240. We also show how to simulate an arbitrary protocol with a protocol using the binary alphabet, a constant factor increase in communication, and tolerating a 1/8 - ϵ fraction of errors.