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 resolve open problems dating back to 1986.

Alexander Sherstov earned his Ph.D. in Computer Science in August 2009 at the University of Texas at Austin, under the direction of Prof. Adam Klivans, and is currently a postdoctoral researcher at Microsoft Research. He has broad research interests in theoretical computer science, including complexity theory, computational learning theory, and quantum computing.