All reports by Author Rahul Jain:

__
TR16-072
| 4th May 2016
__

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha#### Separations in communication complexity using cheat sheets and information complexity

__
TR11-024
| 25th February 2011
__

Rahul Jain#### New strong direct product results in communication complexity

__
TR10-071
| 19th April 2010
__

Rahul Jain, Ashwin Nayak#### The space complexity of recognizing well-parenthesized expressions

Revisions: 4

__
TR07-064
| 19th June 2007
__

Rahul Jain, Hartmut Klauck, Ashwin Nayak#### Direct Product Theorems for Communication Complexity via Subdistribution Bounds

__
TR06-151
| 10th December 2006
__

Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan#### The communication complexity of correlation

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

While exponential separations are known between quantum and randomized communication complexity for partial functions, e.g. Raz [1999], the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized

communication complexity for a ...
more >>>

Rahul Jain

We show two new direct product results in two different models of communication complexity. Our first result is in the model of one-way public-coin model. Let $f \subseteq X \times Y \times Z $ be a relation and $\epsilon >0$ be a constant. Let $R^{1,pub}_{\epsilon}(f)$ represent the communication complexity of ... more >>>

Rahul Jain, Ashwin Nayak

We show an Omega(sqrt(n)/T^3) lower bound for the space required by any

unidirectional constant-error randomized T-pass streaming algorithm that recognizes whether an expression over two types of parenthesis is well-parenthesized. This proves a conjecture due to Magniez, Mathieu, and Nayak

(2009) and rigorously establishes the peculiar power of bi-directional streams ...
more >>>

Rahul Jain, Hartmut Klauck, Ashwin Nayak

A basic question in complexity theory is whether the computational

resources required for solving k independent instances of the same

problem scale as k times the resources required for one instance.

We investigate this question in various models of classical

communication complexity.

We define a new measure, the subdistribution bound, ... more >>>

Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan

We examine the communication required for generating random variables

remotely. One party Alice will be given a distribution D, and she

has to send a message to Bob, who is then required to generate a

value with distribution exactly D. Alice and Bob are allowed

to share random bits generated ...
more >>>