57 citations · 74 across the 6 of their papers we have counts for
Showing quant-phShow all
3 papers · 1 filter
quant-ph2007★ 6 cited
Quantum communication complexity of block-composed functions
Yaoyun Shi, Yufan Zhu
A major open problem in communication complexity is whether or not quantum protocols can be exponentially more efficient than classical protocols on _total_ Boolean functions in th…
quant-ph2005★ 11 cited
Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement
Yaoyun Shi, Yufan Zhu
We initiate the study of quantifying nonlocalness of a bipartite measurement by the minimum amount of classical communication required to simulate the measurement. We derive genera…
quant-ph2005★ 57 cited
The Communication Complexity of the Hamming Distance Problem
Wei Huang, Yaoyun Shi, Shengyu Zhang +1
We investigate the randomized and quantum communication complexity of the Hamming Distance problem, which is to determine if the Hamming distance between two n-bit strings is no le…