Explicit Capacity Approaching Coding for Interactive Communication
Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron‐Zewi, Avi Wigderson · IEEE Transactions on Information Theory · 2018
We show an explicit (that is, efficient and deterministic) capacity approaching interactive coding scheme that simulates any interactive protocol under random errors with nearly optimal communication rate. Specifically, over the binary symmetric channel with crossover probability ϵ, our coding scheme achieves a communication rate of 1- O(√/H(ϵ)), together with negligible exp(-Ω(ϵ4n/logn)) failure probability (over the randomness of the channel). A rate of 1 - Θ(√/H(ϵ)) is likely asymptotically optimal as a result of Kol and Raz (2013) suggests. Prior to this paper, such a communication rate was achievable only using randomized coding schemes [Kol and Raz (2013); Hauepler (2014)].