The Taub Faculty of Computer Science Events and Talks

In a profoundly influential paper, Shannon introduced information theory and used it to study the one-way data transmission problem, initiating the study of data compression. In the last few decades, the study of efficient communication using tools from information theory has led to many interesting results.

In this talk we will focus on the interactive analog of data compression, the interactive compression question: Can we compress interactive communication to its information content? The standard way to formalize this question is by asking whether the communication complexity of any interactive communication task is close to its internal or external information complexity.

We will survey two separation results, showing exponential gaps between the information and communication of explicit interactive communication tasks [GKR14, GKR15]. These results imply that optimal interactive compression is impossible in general.