Conference abstracts

Plenary talk

July 17, 11:30 ~ 12:30

Information Complexity and Applications

Mark Braverman

Princeton University and Institute for Advanced Study, USA   -

Over the past two decades, information theory has reemerged within computational complexity theory as a mathematical tool for obtaining unconditional lower bounds in a number of models, including streaming algorithms, data structures, and communication complexity. Many of these applications can be systematized and extended via the study of information complexity – which treats information revealed or transmitted as the resource to be conserved.

In this talk we will discuss the two-party information complexity and its properties – and the interactive analogues of classical source coding theorems. We will then discuss applications to exact communication complexity bounds, multi-party communication, and quantum communication complexity.

View abstract PDF

FoCM 2017, based on a nodethirtythree design.