Information complexity and applications

Members' Seminar
Topic:Information complexity and applications
Speaker:Mark Braverman
Affiliation:Princeton University; von Neumann Fellow, School of Mathematics
Date:Monday, March 6
Time/Room:2:00pm - 3:00pm/S-101
Video Link:https://video.ias.edu/members/2017/0306-MarkBraverman

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 overview 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, hardness amplification, and quantum communication complexity.