DIMACS Theoretical Computer Science Seminar

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


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.