Information Complexity and Applications

Over the past three decades, communication complexity has found
applications in nearly every area of computer science, and constitutes
one of the few known techniques for proving unconditional lower
bounds. Developing tools in communication complexity is therefore a
promising approach for making progress in other computational models
such as circuit complexity, streaming, data structures, and privacy to
mention a few.

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. This compression theory, however, does not
readily convert to interactive setups, where two (or more) parties
must engage in a multi-round conversation to accomplish a task.

The goal of our ongoing research is to extend this theory, develop the
right tools, and understand how information behaves in interactive
setups, such as the communication complexity model. In this
introductory talk, I will give an overview of Information Complexity,
an interactive analogue of Shannon's theory. I will describe some of
the main open problems in this emerging field, and some of the
interesting applications we found, including an exact bound on the
communication complexity of the Set Disjointness function (~0.48n),
and how information helps us understand the limits of parallel
computation.