Sasha Sherstov talk, Monday, 02/28, 3:30
David Kempe
we are continuing our glut of excellent theory talks with another
faculty candidate. Alexander (Sasha) Sherstov from MSR New England
will give a talk on "Limit of Communication". All the relevant details
are below.
I'm looking forward to seeing many of you at the talk.
Time: Monday, 02/28, 3:30 PM
Location: SAL 101
Speaker: Alexander Sherstov (Microsoft Research)
Title: Limits of Communication
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.
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.
--
David Kempe <dke...@usc.edu>