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)

 

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 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 csc_help@ncsu.edu.

Mediasite Catalog \"\"


Back to Seminar Listings
Back to Colloquia Home Page