EE Seminar, Dr. Rotem Oshman

~~(The talk will be given in English)

Speaker: Dr. Rotem Oshman,
School of Computer Science, Tel Aviv University

Monday, December 8th, 2014
15:00 - 16:00
Room 011, Kitot Bldg., Faculty of Engineering

Communication and Information Lower Bounds for Large-Scale Distributed Computation
Abstract
In large distributed systems, communication between the machines participating in the computation is often the most expensive part of the computation, dwarfing the cost of local computation on each machine. Thus, to understand the cost of large-scale distributed computing, we study the number of bits that must be exchanged to solve a given problem, and also the number of communication rounds.

In this talk I will give an overview of the area, and describe a recent lower bound on a classical problem in communication complexity, called Set Disjointness, where k players each receive a subset of the numbers {1,...,n] and their goal is to determine whether the intersection of all their sets is empty or not. Our lower bound implies lower bounds on several natural problems, such as testing graph connectivity and computing the number of distinct elements in the input). The lower bound is proven using information complexity, an approach that extends classical information theory to the interactive setting where many players communicate back-and-forth in order to accomplish some task.
This is joint work with Mark Braverman, Faith Ellen, Toniann Pitassi and Vinod Vaikuntanathan