Seminars & Colloquia

Alexander Sherstov

Microsoft Research

"Limits of Communication"

Wednesday February 23, 2011 09:30 AM
Location: 3211, EBII NCSU Centennial Campus
(Visitor parking instructions)



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.


Short Bio:

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.

Host: Carla Savage, Computer Science, NCSU

Media Files:
No media files available at this time

Video Presentation: Host is responsible for requesting video recording by filling out this Web form. For other technical issues, contact us at

Mediasite Catalog \"\"

Back to Seminar Listings
Back to Colloquia Home Page