### Special Talk hosted by Michael Saks, Mathematics, Rutgers University

Title: Limits of Communication

Speaker: **Alexander Sherstov**, Microsoft Research

Date: Wednesday, February 2, 2011 3:30 PM

Location: Hill Center, Room 124, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:
Consider a function f whose arguments are distributed
among several parties, making it impossible for any one
party to compute f in isolation. Initiated in 1979,
communication complexity theory studies how many bits of
communication are needed to evaluate f. I will prove that:

(1) some natural and practical problems require high
communication to achieve any advantage at all over
random guessing;
(2) solving n instances of any known communication
problem on a quantum computer incurs Omega(n) times
the cost of a single instance, even to achieve
exponentially small correctness probability.

The proofs work by recasting the communication problem
geometrically and looking at the dual problem in a novel
way. Our results solve open problems dating back to 1986.