91 citations · 766 across the 68 of their papers we have counts for
6 papers · 1 filter
The Partition Bound for Classical Communication Complexity and Query Complexity
Rahul Jain, Hartmut Klauck
We describe new lower bounds for randomized communication complexity and query complexity which we call the partition bounds. They are expressed as the optimum value of linear prog…
Depth-Independent Lower bounds on the Communication Complexity of Read-Once Boolean Formulas
Rahul Jain, Hartmut Klauck, Shengyu Zhang
We show lower bounds of and on the randomized and quantum communication complexity, respectively, of all -variable read-once Boolean formulas. Our res…
QIP = PSPACE
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay +1
We prove that the complexity class QIP, which consists of all problems having quantum interactive proof systems, is contained in PSPACE. This containment is proved by applying a pa…
On the power of a unique quantum witness
Rahul Jain, Iordanis Kerenidis, Greg Kuperberg +3
In a celebrated paper, Valiant and Vazirani raised the question of whether the difficulty of NP-complete problems was due to the wide variation of the number of witnesses of their…
Two-message quantum interactive proofs are in PSPACE
Rahul Jain, Sarvagya Upadhyay, John Watrous
We prove that QIP(2), the class of problems having two-message quantum interactive proof systems, is a subset of PSPACE. This relationship is obtained by means of an efficient para…
New Results in the Simultaneous Message Passing Model
Rahul Jain, Hartmut Klauck
Consider the following Simultaneous Message Passing (SMP) model for computing a relation f subset of X x Y x Z. In this model Alice, on input x in X and Bob, on input y in Y, send…