18 citations · 32 across the 5 of their papers we have counts for
Showing 2007Show all
2 papers · 1 filter
cs.CC2007★ 1 cited
Disjointness is hard in the multi-party number on the forehead model
Troy Lee, Adi Shraibman
We show that disjointness requires randomized communication Omega(n^{1/(k+1)}/2^{2^k}) in the general k-party number-on-the-forehead model of complexity. The previous best lower bo…
quant-ph2007★ 18 cited
Optimal quantum adversary lower bounds for ordered search
Andrew M. Childs, Troy Lee
The goal of the ordered search problem is to find a particular item in an ordered list of n items. Using the adversary method, Hoyer, Neerbek, and Shi proved a quantum lower bound…