Fast Interactive Coding against Adversarial Noise
Fast Interactive Coding against Adversarial Noise
复制标题
针对对抗性噪声的快速交互式编码
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. Naor
中科院分区：
文献类型：
--
作者：
Zvika Brakerski;Y. Kalai;M. Naor
考虑两个希望交流以执行一些交互式协议π的当事方。执行π（是为无错误的通道而设计的）。交互式协议由许多简短消息组成。
Schulman [1992，1993]介绍了交互式编码的概念：一个模拟器，鉴于任何协议π，即使存在恒定的速率对抗通道错误，并且仅具有恒定的恒定，它也能够模拟它（即产生其预期的转录本） （乘法）开销。
在这项工作中，我们提出了三个有效的模拟器，所有模拟器都是随机的，并且具有一定的故障概率（在选择硬币的选择上）。至1/32的对抗误差。 ，具有故障概率1/poly（n），并且对对抗误差的某些恒定分数（在RAM模型中测量了计算复杂性）。 （尤其是对手可能会知道的）。
Consider two parties who wish to communicate in order to execute some interactive protocol π. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant fraction of the bits arbitrarily, thus interrupting the execution of π (which was designed for an error-free channel). If π only contains a single long message, then a good error correcting code would overcome the noise with only a constant overhead in communication. However, this solution is not applicable to interactive protocols consisting of many short messages.
Schulman [1992, 1993] introduced the notion of interactive coding: A simulator that, given any protocol π, is able to simulate it (i.e., produce its intended transcript) even in the presence of constant rate adversarial channel errors, and with only constant (multiplicative) communication overhead. However, the running time of Schulman's simulator, and of all simulators that followed, has been exponential (or subexponential) in the communication complexity of π (which we denote by N).
In this work, we present three efficient simulators, all of which are randomized and have a certain failure probability (over the choice of coins). The first runs in time poly(N), has failure probability roughly 2-N, and is resilient to 1/32-fraction of adversarial error. The second runs in time O(N log N), has failure probability roughly 2-N, and is resilient to some constant fraction of adversarial error. The third runs in time O(N), has failure probability 1/poly(N), and is resilient to some constant fraction of adversarial error. (Computational complexity is measured in the RAM model.) The first two simulators can be made deterministic if they are a priori given a random string (which may be known to the adversary ahead of time). In particular, the simulators can be made to be nonuniform and deterministic (with equivalent performance).