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 |

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.