pith. sign in

arxiv: 1703.07521 · v5 · pith:AOO6FF4Snew · submitted 2017-03-22 · 💻 cs.CC · quant-ph

Lifting randomized query complexity to randomized communication complexity

classification 💻 cs.CC quant-ph
keywords mathrmcirccomplexityrandomizedtimesleftrightcdot
0
0 comments X
read the original 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))$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.