The one-way communication complexity of the Boolean Hidden Matching Problem
Preprint
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].Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- On Randomized One-round Communication Complexitycomputational complexity, 1999
- Lower bounds for one-way probabilistic communication complexity and their application to space complexityTheoretical Computer Science, 1996
- Fourier analysis for probabilistic communication complexitycomputational complexity, 1995
- Étude des coefficients de Fourier des fonctions deAnnales de l'institut Fourier, 1970