Information Complexity and Applications

Speaker: Mark Braverman , Princeton University

Date: Tuesday, November 26, 2013

Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: 32-G449

Event Type:

Room Description:

Host: Constantinos Daskalakis and Dana Moshkovitz

Contact: Holly A Jones,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:

Reminder Subject: TALK: Information Complexity and Applications

Abstract: 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

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Colloquium - 2013.

Created by Holly A Jones Email at Monday, November 18, 2013 at 3:32 PM.