91 citations · 766 across the 68 of their papers we have counts for
4 papers · 1 filter
A strong direct product theorem for two-way public coin communication complexity
Rahul Jain
We show a direct product result for two-way public coin communication complexity of all relations in terms of a new complexity measure that we define. Our new measure is a generali…
Strong direct product conjecture holds for all relations in public coin randomized one-way communication complexity
Rahul Jain
Let f subset of X x Y x Z be a relation. Let the public coin one-way communication complexity of f, with worst case error 1/3, be denoted R^{1,pub}_{1/3}(f). We show that if for co…
The space complexity of recognizing well-parenthesized expressions in the streaming model: the Index function revisited
Rahul Jain, Ashwin Nayak
We show an Omega(sqrt{n}/T) lower bound for the space required by any unidirectional constant-error randomized T-pass streaming algorithm that recognizes whether an expression over…
Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity
Rahul Jain, Hartmut Klauck, Miklos Santha
A Direct Sum Theorem holds in a model of computation, when solving some k input instances together is k times as expensive as solving one. We show that Direct Sum Theorems hold in…