Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR17-054 | 12th July 2017 14:41

Lifting randomized query complexity to randomized communication complexity

RSS-Feed




Revision #3
Authors: Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay
Accepted on: 12th July 2017 14:41
Downloads: 30
Keywords: 


Abstract:

We show that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$ and a function $g:\{0,1\}^{m}\times \{0,1\}^{m} \rightarrow \{0,1\}$ (with $m= O(\log n)$),
$$\mathrm{R}_{1/3}(f\circ g^n) = \Omega\left(\mathrm{R}_{1/3}(f) \cdot \left(\log\frac{1}{\mathrm{disc}(M_g)} - O(\log n)\right)\right),$$
where $f\circ g^n$ represents the composition of $f$ and $g^n$, $M_g$ is the sign matrix for $g$, $\mathrm{disc}(M_g)$ is the discrepancy of $M_g$ under the uniform distribution and $\mathrm{R}_{1/3}(f)$ ($\mathrm{R}_{1/3}(f\circ g^n)$) denotes the randomized query complexity of $f$ (randomized communication complexity of $f\circ g^n$) with worst case error $\frac{1}{3}$.

In particular, this implies that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$, $$\mathrm{R}_{1/3}(f\circ \mathrm{IP}_m^n) = \Omega\left(\mathrm{R}_{1/3}(f) \cdot m\right),$$ where $\mathrm{IP}_m:\{0,1\}^m\times \{0,1\}^m\rightarrow \{0,1\}$ is the Inner Product (modulo $2$) function and $m= O(\log(n))$.



Changes to previous version:

Further elaboration on proofs.


Revision #2 to TR17-054 | 1st July 2017 14:20

Lifting randomized query complexity to randomized communication complexity





Revision #2
Authors: Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay
Accepted on: 1st July 2017 14:20
Downloads: 20
Keywords: 


Abstract:

We show that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$ and a function $g:\{0,1\}^{m}\times \{0,1\}^{m} \rightarrow \{0,1\}$ (with $m= O(\log n)$),
$$\mathrm{R}_{1/3}(f\circ g^n) = \Omega\left(\mathrm{R}_{1/3}(f) \cdot \left(\log\frac{1}{\mathrm{disc}(M_g)} - O(\log n)\right)\right),$$
where $f\circ g^n$ represents the composition of $f$ and $g^n$, $M_g$ is the sign matrix for $g$, $\mathrm{disc}(M_g)$ is the discrepancy of $M_g$ under the uniform distribution and $\mathrm{R}_{1/3}(f)$ ($\mathrm{R}_{1/3}(f\circ g^n)$) denotes the randomized query complexity of $f$ (randomized communication complexity of $f\circ g^n$) with worst case error $\frac{1}{3}$.

In particular, this implies that for a relation $f\subseteq \{0,1\}^n\times \mathcal{O}$, $$\mathrm{R}_{1/3}(f\circ \mathrm{IP}_m^n) = \Omega\left(\mathrm{R}_{1/3}(f) \cdot m\right),$$ where $\mathrm{IP}_m:\{0,1\}^m\times \{0,1\}^m\rightarrow \{0,1\}$ is the Inner Product (modulo $2$) function and $m= O(\log(n))$.



Changes to previous version:

Revised proof.


Revision #1 to TR17-054 | 11th April 2017 14:36

Lifting randomized query complexity to randomized communication complexity





Revision #1
Authors: Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay
Accepted on: 11th April 2017 14:36
Downloads: 72
Keywords: 


Abstract:

This paper has been withdrawn due to an incorrigible error.


Paper:

TR17-054 | 22nd March 2017 07:00

Lifting randomized query complexity to randomized communication complexity


Abstract:

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 of $y$).

Our proof follows on the lines of Raz and Mckenzie [RM99] (and its generalization due to [GPW15]), who showed a lifting theorem for deterministic query complexity to deterministic communication complexity. Our proof deviates from theirs in an important fashion that we consider partitions of rectangles into many sub-rectangles, as opposed to a particular sub-rectangle with desirable properties, as considered by Raz and McKenzie. As a consequence of our main result, some known separations between quantum and classical communication complexities follow from analogous separations in the query world.



ISSN 1433-8092 | Imprint