Omri Weinstein: Interactive Information Complexity and Applications

Abstract: Over the past three decades, communication complexity has been extensively used to capture the
fundamental limitations in diverse areas of theoretical computer science and modern computing systems.
In the first part of this talk, I will describe some of the tools and applications we developed in
Information Complexity, which can be viewed as an "interactive extension" of Shannon's information theory.
    
The second part of the talk explores the role of interaction in economics and decentralized equilibrium 
computation. Specifically, we study the communication complexity of finding an *approximate* Nash equilibrium 
in a 2-player game, one of the most important problems in algorithmic game theory. Our result implies that  
there is no market dynamic that converges even to an approximately stable state in sub-polynomial time.