Efficient Interactive Coding against Adversarial Noise
Efficient Interactive Coding against Adversarial Noise
复制标题
针对对抗性噪声的高效交互式编码
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Y. Kalai
中科院分区：
文献类型：
--
作者：
Zvika Brakerski;Y. Kalai
在这项工作中，我们研究了对噪声稳健的交互式协议的问题，这是Schulman的第二件作品（FOCS '92，STOC '93）最初考虑的问题，最近仍然很受欢迎。错误校正代码的交互式类似物：给定一个交互式协议，该协议旨在在无误差通道上运行，构建一个评估相同函数的协议（或更一般而言，更一般地模拟在噪声通道上执行原始协议。错误。并以概率至少1-2 -ω（CC）模拟原始协议的成功。
In this work, we study the problem of constructing interactive protocols that are robust to noise, a problem that was originally considered in the seminal works of Schulman (FOCS '92, STOC '93), and has recently regained popularity. Robust interactive communication is the interactive analogue of error correcting codes: Given an interactive protocol which is designed to run on an error-free channel, construct a protocol that evaluates the same function (or, more generally, simulates the execution of the original protocol) over a noisy channel. As in (non-interactive) error correcting codes, the noise can be either stochastic, i.e. drawn from some distribution, or adversarial, i.e. arbitrary subject only to a global bound on the number of errors. We show how to efficiently simulate any interactive protocol in the presence of constant-rate adversarial noise, while incurring only a constant blow-up in the communication complexity (CC). Our simulator is randomized, and succeeds in simulating the original protocol with probability at least 1 - 2-Ω(CC).