Events Calendar

Alexander Sherstov (UCLA): Limits of Multiparty Communication

Speaker: Alexander Sherstov, UCLA

Talk Title: Limits of Multiparty Communication

Series: CS Colloquium

Abstract: Communication complexity theory studies the following question: how many bits of communication are required to compute a Boolean function f whose arguments are distributed among several parties, possibly with overlap? Apart from being a natural subject of study in its own right, communication complexity sheds light on various questions in the theory of computing that do not seem to involve communication in any way.

A function f of basic importance in the area is the so called disjointness function, which evaluates to true when its arguments are sets with empty intersection. The multiparty communication requirements of this function have been actively studied since the late 1980s, with only very partial results available. In this work, we essentially resolve the question in its entirety.

PAPER URL: http://eccc.hpi-web.de/report/2011/145

Biography: Alexander Sherstov completed his Ph.D. at the University of Texas at Austin, under the direction of Adam Klivans. After a two-year postdoc at Microsoft Research, Sherstov joined the Computer Science Department at UCLA last year as an assistant professor. He has broad research interests in theoretical computer science, including computational complexity, computational learning, and quantum computing.

Host: Shaddin Dughmi

Location: SSL 150

Audiences: Everyone Is Invited

Contact: Assistant to CS chair