11 citations · 15 across the 3 of their papers we have counts for
3 papers
cs.IT2008
New bounds on classical and quantum one-way communication complexity
Rahul Jain, Shengyu Zhang
In this paper we provide new bounds on classical and quantum distributional communication complexity in the two-party, one-way model of communication. In the classical model, our b…
quant-ph2005★ 4 cited
(Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids
Shengyu Zhang
The Local Search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to many areas in computer science an…
quant-ph2003★ 11 cited
On the power of Ambainis's lower bounds
Shengyu Zhang
The polynomial method and the Ambainis's lower bound (or \emph{Alb}, for short) method are two main quantum lower bound techniques. While recently Ambainis showed that the polynomi…