Omri Weinstein: Information Complexity, Direct Sums and Products and the Quest for Interactive Compression

Over the past three decades, communication complexity had a profound impact on nearly every field of theoretical computer science, and constitutes one of the few known methods for proving unconditional lower bounds. As such, developing new tools in communication complexity is a promising approach for making progress in other computational models, such as circuit complexity, streaming algorithms, property testing, data structures and VLSI chip design.

One striking example of such tool is information theory, introduced by Shannon in the late 1940's in the context of the one way data transmission problem. Shannon's work revealed the intimate connection between information and communication, namely, that the amortized transmission cost of a random message is equal to the amount of information it contains. Classical information theory, however, does not readily convert to interactive setups, where two (or more) parties must engage in a multi-round conversation in order to accomplish a desirable task.

In this talk I will give an introduction to Information Complexity, an interactive analogue of Shannon's information theory, which has recently found many applications in theoretical computer science and in particular for proving "black-box" hardness results (hardness amplification), also known as Direct Sum and Product theorems. In the communication complexity model, proving such theorems turns out to be equivalent to the question of whether Shannon's compression theory indeed extends to the *interactive* setup.

I will survey some of the exciting recent progress in the field, including upper and lower bounds for the fascinating problem of interactive compression, and its practical and philosophical implications to computer science and beyond.

No prior knowledge will be assumed in this talk.