Gillat Kol: Interactive Compression

Friday, December 4, 2015 - 1:30pm to 4:30pm
Pizza at 1:15p
D-463 Star
Gillat Kol
Abstract:  In profoundly influential works, Shannon and Huffman showed that if Alice
wants to send a message X to Bob, it's sufficient for her to send roughly
H(X) bits, where H denotes Shannon's entropy function. This means that
every message can be compressed to its information content. Can one prove
similar results in the interactive setting, where Alice and Bob engage in
an interactive communication protocol? The standard way to formalize this
question is by asking whether the communication complexity of a
communication task is always (roughly) bounded by its (internal or
external) information complexity.

In this talk, we will survey known compression protocols and see that for
some interesting special cases, interactive compression is possible (e.g.
[Kol15]). We then sketch the proof of [GKR15], showing that interactive
compression is impossible in general, by presenting a communication task
whose communication complexity is exponentially large in its (external)
information cost.