63 citations · 124 across the 20 of their papers we have counts for
Showing 2006 · quant-phShow all
2 papers · 2 filters
quant-ph2006
Exponential separations for one-way quantum communication complexity, with applications to cryptography
Dmytro Gavinsky, Julia Kempe, Iordanis Kerenidis +2
We give an exponential separation between one-way quantum and classical communication protocols for a partial Boolean function (a variant of the Boolean Hidden Matching Problem of…
quant-ph2006★ 5 cited
The one-way communication complexity of the Boolean Hidden Matching Problem
Iordanis Kerenidis, Ran Raz
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…