Open Lecture — Interactive Information: Applications and New Directions

In 1948, Shannon laid the foundations for information theory — the study of one-way data transmission over a channel. Communication complexity, developed in the last thirty years, studies the communication cost of functions, and has a vast number of applications in computer science. In the standard communication setting, two players (Alice and Bob) need to transmit data to one another via an interactive protocol, in order to compute some joint function of their inputs. The communication complexity is the minimal number of bits that Alice and Bob need to transmit in order to solve their problem.

In the last ten years, the theory of interactive information has been developed, generalizing both information theory, and communication complexity. The goal is to understand how much information Alice and Bob need to reveal to one another in order to solve their problem. Interactive information complexity has emerged as a major tool in the study of communication complexity, and insights from interactive information theory have led to the resolution of many of the open problems in communication complexity.

In this talk, we will focus on a few important applications of interactive information complexity, including data privacy, distributed computing, and complexity theory. We will then discuss new directions and open problems in the foundations of interactive information theory.

Light refreshments will be served before the lecture at 3:30 p.m.