Coding for Interactive Communication
A survey on recent progress

Madhu Sudan (Microsoft Research)

In a seminal work in 1992, Schulman raised the question of whether an interaction can be protected from errors that occur on a noisy channel. He also gave some surprisingly positive answers showing that a constant fraction of adversarial errors can be corrected while incurring only a constant factor blowup in the number of bits exchanged. 

Recently this line of research was revived by the works of Braverman and Rao (2009), who gave essentially optimal results on the fraction of errors that could be corrected. Both the above papers rely on a combinatorial structure called a tree code for which efficient construction and decoding algorithms are not known - as a result all the previous papers led to algorithmically inefficient results. This was remedied to some extent by Brakerski and Kalai who injected a new idea that also suggested ways of achieving many of the results algorithmically with use only of small tree codes.  Very recently Haeupler and Ghaffari building on works by Braverman and Efremenko and the above mentioned papers gave algorithmically efficient results matching all the known information-theoretic limits. Along the way Haeupler also gives a solution to the Interactive Communication problem without any tree codes. 

In this talk I will survey some of the main ideas behind the results (to the best of my understanding).