EE Seminar: The Role of Interaction in Streaming, Economics and Parallel Computing

~~(The talk will be given in English)

Speaker:  Dr. Omri Weinstein
                   New York University

Wednesday, December 9th, 2015
15:00 - 16:00
Room 011, Kitot Bldg., Faculty of Engineering

The Role of Interaction in Streaming, Economics and Parallel Computing
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 (e.g., "MapReduce") platforms, data streaming, economic markets and social and physical networks.
In this talk I will describe new tools and applications of communication complexity to streaming, economics and parallelization: We prove tight bounds on the fundamental problem of approximating the "frequency moments" of a data stream, one of the most important problems in real-time monitoring of network traffic. We will then see how information and communication complexity improved our understanding of the power and limitations of parallel computing. Finally, we will explore the economic problem of distributed equilibrium computation. Our result implies that any market dynamic that converges even to an approximately stable market state, requires exponential communication in the size of the market.

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 interactive communication and parallel computing, economics and privacy. 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.