Efficient interactive coding against adversarial noise

In this talk we will 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^{-Omega(cc)}.

Joint work with Zvika Brakerski
.
http://theory.csail.mit.edu/reading-group/