Coding for Interactive Communication Made Easy and Communication Efficient (or "How to make conversations robust to noise.")
September 10, 2014
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 (except for recent work of [Kol, Raz, STOC13] which only works for more benign random noise).
This talk will introduce a 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 are possible. It 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.
This will be an interactive board talk. ;) Come and participate!
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 (except for recent work of [Kol, Raz, STOC13] which only works for more benign random noise).
This talk will introduce a 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 are possible. It 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.
This will be an interactive board talk. ;) Come and participate!