91 citations · 766 across the 68 of their papers we have counts for
4 papers · 1 filter
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…
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…
A parallel approximation algorithm for mixed packing and covering semidefinite programs
Rahul Jain, Penghui Yao
We present a parallel approximation algorithm for a class of mixed packing and covering semidefinite programs which generalize on the class of positive semidefinite programs as con…
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…