1.2k citations · 2.5k across the 41 of their papers we have counts for
Showing 2006 · quant-phShow all
2 papers · 2 filters
quant-ph2006★ 5 cited
Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function
Dmytro Gavinsky, Julia Kempe, Ronald de Wolf
We give an exponential separation between one-way quantum and classical communication complexity for a Boolean function. Earlier such a separation was known only for a relation. A…
quant-ph2006★ 13 cited
Strengths and Weaknesses of Quantum Fingerprinting
Dmytro Gavinsky, Julia Kempe, Ronald de Wolf
We study the power of quantum fingerprints in the simultaneous message passing (SMP) setting of communication complexity. Yao recently showed how to simulate, with exponential over…