BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Quantum one-way communication can be exponentially stronger than c
 lassical communication - Regev\, O (Tel Aviv)
DTSTART:20110329T090000Z
DTEND:20110329T100000Z
UID:TALK30445@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:In STOC 1999\, Raz presented a (partial) function for which th
 ere is a quantum protocol communicating only O(log n) qubits\, but for whi
 ch any classical (randomized\, bounded-error) protocol requires poly(n) bi
 ts of communication.  That quantum protocol requires two rounds of communi
 cation. Ever since Raz's paper it was open whether the same exponential se
 paration can be achieved with a quantum protocol that uses only one round 
 of communication. In other words\, can quantum one-way communication be ex
 ponentially stronger than classical two-way communication? Here we settle 
 this question in the affirmative.\n\nBased on joint work with Bo'az Klarta
 g.\n\nNOTE: This talk is about lower bounds for *classical* communication 
 complexity\; no knowledge of quantum communication complexity is assumed o
 r required.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR