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
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.