Fast algorithms for interactive coding

Consider two parties who wish to communicate in order to execute some interactive protocol pi. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant fraction of the bits as he pleases, thus interrupting the execution of pi (which was designed for an errorless channel). If pi only contains a single long message, then a good error correcting code would overcome the noise with only a constant overhead in communication. However, this solution is not applicable to interactive protocols consisting of many short messages. Schulman (FOCS 92, STOC 93) presented the notion of interactive coding: A simulator that, given any protocol pi, is able to simulate it (i.e. produce its intended transcript) even with con-stant rate adversarial channel errors, and with only constant (multiplicative) communication over-head. Until recently, however, the running time of all known simulators was exponential (or sub-exponential) in the communication complexity of pi (denoted N in this work). Brakerski and Kalai (FOCS 12) recently presented a simulator that runs in time poly(N). Their simulator is randomized (each party flips private coins) and has failure probability roughly 2−N. In this work, we improve the computational complexity of interactive coding. While at least N computational steps are required (even just to output the transcript of pi), the BK simulator runs in time Ω̃(N2). We present two efficient algorithms for interactive coding: The first with computational com-plexity O(N logN) and exponentially small (in N) failure probability; and the second with com-putational complexity O(N), but failure probability 1/poly(N). (Computational complexity is measured in the RAM model.