Tel-Aviv University - Computer Science Colloquium
Sunday, November 29, 14:15-15:15
at 14:00 Alice and Bob want to play cards over the phone. To start the game each of them should choose a set of ten random cards, and of course the two sets have to be disjoint. How much communication between Alice and Bob is needed to achieve this task?
In the talk I will define the sampling communication complexity model, which generalizes the above example. We will then study this problem in the classical and quantum communication complexity models. We will discover:
1) An exponential gap between the quantum and classical sampling complexity. This is the first provable exponential gap known between quantum and classical computations.
2) A new interpretation for the Log-Rank Conjecture . which is a long standing open problem in classical communication complexity (details in the talk).
3) A tight characterization of the complexity of approximating a super-position, which is a central question in Quantum Information theory.
I do not assume previous background. I will try to explain the basic notions of quantum computation and quantum communication complexity.
Joint work with Andris Ambainis, Leonard Schulman, Umesh Vazirani and Avi Wigderson.
For colloquium schedule, see http://www.math.tau.ac.il/~matias/colloq.html