BEGIN:VCALENDAR
METHOD:PUBLISH
PRODID:-//Apple Computer\, Inc//iCal 1.0//EN
X-WR-CALNAME;VALUE=TEXT:USC
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION:Speaker: Sasha Alexander Sherstov, Microsoft Research
Talk 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:\n
\n
1. some natural and practical problems require high communication to achieve any advantage at all over random guessing;\n
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.\n
\n
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.\n
\n
Biography: 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: Prof. Ming-Deh Huang
SEQUENCE:5
DTSTART:20110228T153000
LOCATION: SAL 101
DTSTAMP:20110228T153000
SUMMARY:CS Colloquium
UID:EC9439B1-FF65-11D6-9973-003065F99D04
DTEND:20110228T130000
END:VEVENT
END:VCALENDAR