Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with hidden matching:
TR04-036 | 27th March 2004
Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis

Exponential Separation of Quantum and Classical One-Way Communication Complexity

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM_n: Alice gets as input a string x in {0,1}^n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple (i,j,b) ... more >>>

ISSN 1433-8092 | Imprint