Computer Sciences Colloquium: The Role of Interaction in Economics and Parallel Computation

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, such as distributed platforms, economic markets, streaming models and social and physical networks. In the first part of this talk I will describe some of the concepts and tools we developed in Information Complexity, which can be viewed as an "interactive" analogue of Shannon's information theory, and how these tools significantly improved our understanding of the power and limitations of parallel computing. In the second part of the talk, I will describe applications of communication complexity to decentralized equilibrium computation and market dynamics. Specifically, we study the communication complexity of finding an *approximate* Nash equilibrium in a 2-player game, arguably the most important problem in algorithmic game theory. In contrast to the exact equilibrium case (Hart and Mansour, STOC '07), we show an exponential gap between the deterministic non-deterministic communication complexity of reaching approximate equilibria, eliminating the possibility of an efficient decentralized procedure for this fundamental problem. The heart of our result is an essentially tight communication lower bound on the geometric problem of finding an approximate fixed-point of a composition of two functions. 

Bio:

Omri Weinstein is a Simons Society Junior fellow, hosted by Courant Institute (NYU). He obtained his PhD from Princeton University, under the supervision of Mark Braverman, and holds a BSc in mathematics and computer science from Tel-Aviv University. His main research lies in the intersection between communication and information theory and their applications to economics, privacy and parallel computation. He has done foundational work in the emerging field of Information Complexity and its applications. His awards include the Simons Society fellowship, the Simons graduate award in Theoretical Computer Science and the Siebel scholarship.