## Information complexity and applications

Mark Braverman

Princeton University; von Neumann Fellow, School of Mathematics

March 6, 2017

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.