Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-043 | 1st December 2012 02:33

Efficient Interactive Coding Against Adversarial Noise

RSS-Feed




Revision #1
Authors: Zvika Brakerski, Yael Tauman Kalai
Accepted on: 1st December 2012 02:33
Downloads: 945
Keywords: 


Abstract:

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 \emph{efficiently} simulate any interactive protocol in the presence of constant-rate \emph{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^{-\Omega(CC)}$. (Prior works
could not achieve efficient simulation in the adversarial case.)



Changes to previous version:

Minor changes.


Paper:

TR12-043 | 16th April 2012 07:28

Efficient Interactive Coding Against Adversarial Noise





TR12-043
Authors: Zvika Brakerski, Yael Tauman Kalai
Publication: 20th April 2012 11:00
Downloads: 2830
Keywords: 


Abstract:

In this work, we study the fundamental 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^{-\Omega(CC)}$.

Previous solutions are either inefficient or are resilient only to stochastic noise.



ISSN 1433-8092 | Imprint