## Efficient Interactive Coding Against Adversarial Noise

by Zvika Brakerski and Yael Tauman Kalai

#### Oded's comments

I have been intrigued by the problem of error-resilient communication
protocols ever since Schulman's papers of the early 1990s. Building
on an exponential-time construction of Braverman and Rao (2011),
the current paper provides an optimal solution to this problem,
where optimality is up to the constant (adversarial) error rate.
The construction is by a reduction from any exponential-time construction;
it follows the `good old' paradigm of applying the base construction
on logarithmically long chunks, but of course has to deal with the
various problems that arise (as the adversary may target this structure).
Section 1.3 of the paper gives a good overview of how this can be done.

#### The original abstract

See ECCC TR12-043.

Back to
list of Oded's choices.