Bridging the Capacity Gap Between Interactive and One-Way Communication

We study the communication rate of coding schemes for interactive communication that transform any two-party interactive protocol into a protocol that is robust to noise. Recently, Haeupler (FOCS '14) showed that if an $ε> 0$ fraction of transmissions are corrupted, adversarially or randomly, then it is possible to achieve a communication rate of $1 - \widetilde{O}(\sqrtε)$. Furthermore, Haeupler conjectured that this rate is optimal for general input protocols. This stands in contrast to the classical setting of one-way communication in which error-correcting codes are known to achieve an optimal communication rate of $1 - Θ(H(ε)) = 1 - \widetildeΘ(ε)$. In this work, we show that the quadratically smaller rate loss of the one-way setting can also be achieved in interactive coding schemes for a very natural class of input protocols. We introduce the notion of average message length, or the average number of bits a party sends before receiving a reply, as a natural parameter for measuring the level of interactivity in a protocol. Moreover, we show that any protocol with average message length $\ell = Ω(\mathrm{poly}(1/ε))$ can be simulated by a protocol with optimal communication rate $1 - Θ(H(ε))$ over an oblivious adversarial channel with error fraction $ε$. Furthermore, under the additional assumption of access to public shared randomness, the optimal communication rate is achieved ratelessly, i.e., the communication rate adapts automatically to the actual error rate $ε$ without having to specify it in advance. This shows that the capacity gap between one-way and interactive communication can be bridged even for very small (constant in $ε$) average message lengths, which are likely to be found in many applications.