23 citations · 97 across the 22 of their papers we have counts for
4 papers · 1 filter
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…
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…