ECCC-Report TR06-087https://eccc.weizmann.ac.il/report/2006/087Comments and Revisions published for TR06-087en-usWed, 26 Jul 2006 19:14:30 +0300
Paper TR06-087
| The one-way communication complexity of the Boolean Hidden Matching Problem |
Iordanis Kerenidis,
Ran Raz
https://eccc.weizmann.ac.il/report/2006/087We 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].
Wed, 26 Jul 2006 19:14:30 +0300https://eccc.weizmann.ac.il/report/2006/087