Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Compression of Interactive Communication
event speaker icon
Anat Ganor (​Weizmann Institute of Science)
event date icon
Wednesday, 02.11.2016, 12:30
event location icon
Taub 201
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.