activity
20002009
most citedQuantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

1 citations · 1 across the 6 of their papers we have counts for

collaborators
Showing 2009Show all

2 papers · 1 filter

cs.CC2009

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…

cs.DC2009

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…