91 citations · 766 across the 68 of their papers we have counts for
Showing 2012 · cs.CCShow all
3 papers · 2 filters
cs.CC2012★ 19 cited
A strong direct product theorem in terms of the smooth rectangle bound
Rahul Jain, Penghui Yao
A strong direct product theorem states that, in order to solve k instances of a problem, if we provide less than k times the resource required to compute one instance, then the pro…
cs.CC2012★ 5 cited
Correlation/Communication complexity of generating bipartite states
Rahul Jain, Yaoyun Shi, Zhaohui Wei +1
We study the correlation complexity (or equivalently, the communication complexity) of generating a bipartite quantum state . When is a pure state, we completely characteriz…
cs.CC2012★ 11 cited
A direct product theorem for bounded-round public-coin randomized communication complexity
Rahul Jain, Attila Pereszlenyi, Penghui Yao
In this paper, we show a direct product theorm in the model of two-party bounded-round public-coin randomized communication complexity. For a relation f subset of X times Y times Z…