63 citations · 124 across the 20 of their papers we have counts for
Showing 2006Show all
2 papers · 1 filter
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…