A Composition Theorem for Randomized Query Complexity

Abstract

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\to \{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$. We also show that $R_{1/3}\left(f\circ {\left(g_{O(\log n)}^{\oplus }\right)}^n\right)=\Omega (\log n\cdot R_{4/9}(f)\cdot R_{1/3}(g))$, where $g_{O(\log n)}^{\oplus }$ is the function obtained by composing the xor function on $O(\log n)$ bits and $g^t$.

11 pages; version 2, minor errors corrected