Lifting randomized query complexity to randomized communication complexity

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\to \{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\to \{0,1\}$ is the Inner Product (modulo $2$) function and $m=O(\log (n))$.

We withdraw this paper due to an incorrigible error in the main proof

Cited by in corpus (1)

• Complexity Theory, Game Theory, and Economics: The Barbados Lectures