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.