Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-087 | 25th July 2006 00:00

The one-way communication complexity of the Boolean Hidden Matching Problem

RSS-Feed




TR06-087
Authors: Iordanis Kerenidis, Ran Raz
Publication: 26th July 2006 19:14
Downloads: 1242
Keywords: 


Abstract:

We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for partial functions. A similar result was independently obtained by Gavinsky, Kempe, de Wolf [GKdW06].

Our lower bound is obtained by Fourier analysis, using the Fourier coefficients inequality of Kahn Kalai and Linial [KKL88].



ISSN 1433-8092 | Imprint