TCS+ Online Seminar

Coding for Interactive Communication Made Communication Efficient and Easy (or "How to Make Conversations Robust to Noise.")

Interactive coding schemes add redundancy to any interactive protocol (=conversation) such that it can be reliably performed over a noisy channel which corrupts any eps fraction of the transmitted symbols.

The fact that such coding schemes even exist is a surprising result of Schulman. His and most subsequent coding schemes achieve this feat by using tree-codes, intricate structures with no known efficient construction. This leads to even more complex protocols if computational efficiency is desired. The biggest drawback however is that all these schemes introduce large unspecified constant factor overheads in their communication and thus have tiny communication rates.

This talk will introduce an new, extremely simple, and natural coding scheme that removes all these complications. The protocol essentially consist of both parties having their original conversation as-is (no coding at all!!), interspersed only by short exchanges of hash values. When hash values do not match, the parties backtrack. We feel the protocol gives the simplest explanation for how and why interactive coding schemes for adversarial noise are possible. Our coding scheme furthermore achieves a communication rate of 1 - Theta(sqrt{eps log log 1/eps}) making it the first communication efficient coding scheme against adversarial noise. Interestingly, its communication rate even outperforms the rate for random noise of [Kol, Raz, STOC13] and, despite its odd form, is conjectured to be optimal.