ICM 2014: Mark Braverman on interactive information theory

[Boaz’s note: videos of all ICM 2014 talks, including Mark’s talk discussed below, as well as the talks of  Candes and Bhargava I mentioned before are available online here. In particular, if you still don’t know how one constructs a fully homomorphic encryption scheme then you should (a) be ashamed of yourself and (b) watch Craig Gentry’s talk to see a description of a simple scheme due to him, Sahai and Waters that will close this gap in your education. ]

Guest post by Mark Braverman

My survey covers recent developments in the area of interactive coding theory. This area has been quite active recently, with at least 4 papers on the topic appearing in the next FOCS. This level of activity means that parts of the survey will probably become obsolete within a few years (in fact, I had to rewrite parts of it when the separation result by Ganor, Kol, and Raz was announced in April. [See also this newer result that was posted after Mark sent me his text –Boaz]

The basic premise of interactive coding theory is extending the reach of classical coding and information theory to interactive scenarios. Broadly speaking “coding” encompasses compression (aka noiseless coding), error correction (over both adversarial and randomized channels), and cryptography. The latter does not really fit with the rest of the agenda, since cryptographic protocols have always been interactive.

The interactive version of noiseless coding is communication complexity – and taking the information-theoretic view to it yields information complexity, which behaves as the interactive analogue of Shannon’s entropy. The analogue of Shannon’s Noiseless Coding Theorem holds in the interactive case. To what extent interactive compression is possible (i.e. to what extent the interactive analogue of Huffman Coding exists) is a wide-open problem.

On the noisy side, much progress has been made in the adversarial model, starting with the seminal work of Schulman in the 1990s. Many problems surrounding the interactive analogue of Shannon’s channel capacity, even for simple channels, such as the Binary Symmetric Channel remain open.

For the current state of affairs (surveyed for a Math audience) see my ICM survey which is available here.