Title: Classical Interaction Cannot Replace a Quantum Message
Speaker: Dmitry Gavinsky
Date: Wednesday, April 2, 2008 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We demonstrate a communication task between two players, Alice and Bob, that can be solved by Alice sending one short quantum message to Bob, whilst any classical *interactive* protocol for the problem requires exponentially more communication.
The result is going to appear in the upcoming STOC.