The Optimal Error Resilience of Interactive Communication over the Binary Alphabet

In interactive coding, Alice and Bob wish to compute some function f of their private inputs x and y. They do this by engaging in a non-adaptive (fixed speaking order, fixed length) protocol to jointly compute f(x,y). The goal is to do this in an error-resilient way, such that even if some fraction of the communication is adversarially corrupted, both parties still learn f(x,y).

We consider an adversary who can cause errors, meaning that communicated bits can be flipped adversarially, and study the optimal error resilience of such a protocol. While the optimal error resilience over large alphabets is well understood, the situation over the binary alphabet has remained open. Prior to our works, the best known construction achieved resilience to a 5/39 fraction of errors, while the tightest upper bound was 1/6. The exact value of the optimal error resilience attainable was still unknown. In this talk, I will discuss a new protocol that achieves the optimal error resilience of 1/6. This protocol has the following additional desirable properties: the total communication is only a constant multiplicative factor larger than the communication of the noiseless protocol, and the computation time of Alice and Bob to simulate the noiseless transcript is linear (up to log factors) in the communication of the noiseless protocol.

Based on joint work with Meghal Gupta.