Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > RAHUL JAIN:
All reports by Author Rahul Jain:

TR21-078 | 8th June 2021
Rahul Jain, Srijita Kundu

A direct product theorem for quantum communication complexity with applications to device-independent QKD

We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity of an l-player predicate V. In particular we show that for a distribution p that is product across the input sets of the l players, the success probability of any entanglement-assisted quantum communication protocol for computing n ... more >>>


TR20-131 | 20th August 2020
Rahul Jain, Srijita Kundu

A Direct Product Theorem for One-Way Quantum Communication

We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}. For any \varepsilon, \zeta > 0 and any k\geq1, we show that

\mathrm{Q}^1_{1-(1-\varepsilon)^{\Omega(\zeta^6k/\log|\mathcal{Z}|)}}(f^k) = \Omega\left(k\left(\zeta^5\cdot\mathrm{Q}^1_{\varepsilon + 12\zeta}(f) - \log\log(1/\zeta)\right)\right),

where \mathrm{Q}^1_{\varepsilon}(f) represents the one-way entanglement-assisted quantum communication complexity of f with ... more >>>


TR17-123 | 2nd August 2017
Dmytro Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Quadratically Tight Relations for Randomized Query Complexity

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 >>>


TR17-107 | 1st June 2017
Anurag Anshu, Dmytro Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

A Composition Theorem for Randomized Query complexity

Revisions: 1

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 >>>


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

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 xth bit ... more >>>


TR16-070 | 24th April 2016
Mika Göös, Rahul Jain, Thomas Watson

Extension Complexity of Independent Set Polytopes

Revisions: 1

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 >>>


TR15-199 | 7th December 2015
Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan

Relaxed partition bound is quadratically tight for product distributions

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 >>>


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

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 >>>


TR13-158 | 18th November 2013
Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta

Information-theoretic approximations of the nonnegative rank

Revisions: 3

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 >>>


TR11-033 | 8th March 2011
Rahul Jain, Shengyu Zhang

The influence lower bound via query elimination

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 >>>




ISSN 1433-8092 | Imprint