All reports by Author Rahul Jain:

__
TR17-123
| 2nd August 2017
__

Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs#### Quadratically Tight Relations for Randomized Query Complexity

__
TR17-107
| 1st June 2017
__

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal#### A Composition Theorem for Randomized Query complexity

Revisions: 1

__
TR17-054
| 22nd March 2017
__

Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay#### Lifting randomized query complexity to randomized communication complexity

Revisions: 4

__
TR16-070
| 24th April 2016
__

Mika Göös, Rahul Jain, Thomas Watson#### Extension Complexity of Independent Set Polytopes

Revisions: 1

__
TR15-199
| 7th December 2015
__

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan#### Relaxed partition bound is quadratically tight for product distributions

__
TR15-028
| 27th February 2015
__

Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland#### Relative Discrepancy does not separate Information and Communication Complexity

__
TR13-158
| 18th November 2013
__

Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta#### Information-theoretic approximations of the nonnegative rank

Revisions: 3

__
TR11-033
| 8th March 2011
__

Rahul Jain, Shengyu Zhang#### The influence lower bound via query elimination

Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized query complexity $R_0(f)$: $C(f) \leq R_0(f) \leq C(f)^2$. In this paper we study a new complexity measure that we call expectational certificate complexity $EC(f)$, which is ... more >>>

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

Let the randomized query complexity of a relation for error probability $\epsilon$ be denoted by $\R_\epsilon(\cdot)$. We prove that for any relation $f \subseteq \{0,1\}^n \times \mathcal{R}$ and Boolean function $g:\{0,1\}^m \rightarrow \{0,1\}$, $\R_{1/3}(f\circ g^n) = \Omega(\R_{4/9}(f)\cdot\R_{1/2-1/n^4}(g))$, where $f \circ g^n$ is the relation obtained by composing $f$ and $g$. ... more >>>

Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay

We show that for any (partial) query function $f:\{0,1\}^n\rightarrow \{0,1\}$, the randomized communication complexity of $f$ composed with $\mathrm{Index}^n_m$ (with $m= \poly(n)$) is at least the randomized query complexity of $f$ times $\log n$. Here $\mathrm{Index}_m : [m] \times \{0,1\}^m \rightarrow \{0,1\}$ is defined as $\mathrm{Index}_m(x,y)= y_x$ (the $x$th bit ... more >>>

Mika Göös, Rahul Jain, Thomas Watson

We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $\Omega(n/\log n)$. Previously, no explicit examples of $n$-dimensional $0/1$-polytopes were known with extension complexity larger than exponential in $\Theta(\sqrt{n})$. Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit ... more >>>

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan

Let $f : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ be a 2-party function. For every product distribution $\mu$ on $\{0,1\}^n \times \{0,1\}^n$, we show that $${{CC}}^\mu_{0.49}(f) = O\left(\left(\log {{rprt}}_{1/4}(f) \cdot \log \log {{rprt}}_{1/4}(f)\right)^2\right),$$ where ${{CC}^\mu_\varepsilon(f)$ is the distributional communication complexity with error at most $\varepsilon$ under the distribution $\mu$ and ... more >>>

Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland

Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Recently, Ganor et al. provided such a separation in the distributional setting for a specific input distribution ?. We show that ... more >>>

Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta

Common information was introduced by Wyner as a measure of dependence of two

random variables. This measure has been recently resurrected as a lower bound on the logarithm of the nonnegative rank of a nonnegative matrix. Lower bounds on nonnegative rank have important applications to several areas such

as communication ...
more >>>

Rahul Jain, Shengyu Zhang

We give a simpler proof, via query elimination, of a result due to O'Donnell, Saks, Schramm and Servedio, which shows a lower bound on the zero-error randomized query complexity of a function $f$ in terms of the maximum influence of any variable of $f$. Our lower bound also applies to ... more >>>