Time+Place: Wednesday 06/01/2016 14:30 Room 337-8 Taub Bld.
Title: The Role of Interaction in Economics and Parallel Computation
Speaker: Omri Weinstein - CS-Lecture - Note unusual day http://www.cs.princeton.edu/~oweinste/
Affiliation: Courant Institute (NYU)
Host: Eyal Kushilevitz

Abstract:

Over the past three decades, communication complexity has been extensively
used to capture the fundamental limitations in diverse areas of computer 
science and modern computing systems, such as distributed platforms,
streaming models, economic markets and social and physical networks.
    In the first part of this talk I will give an overview of the
concepts and tools we developed in Information Complexity, which can be
viewed as an "interactive extension" 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 economic optimization problems and to
decentralized equilibrium computation. Specifically, we study the amount 
of communication required to find an *approximate* Nash equilibrium in
2-player (and k-player) games, one of the most important problems in
algorithmic game theory. Our results indicate that any adaptive market
dynamic that converges even to an approximately stable market state,
requires a lot of communication.

Short 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. His awards
include the Simons Society fellowship, the Simons graduate award in
Theoretical Computer Science and the Siebel scholarship.