A Composition Theorem for Randomized Query Complexity

Let the randomized query complexity of a relation for error probability $ϵ$ be denoted by $R_{ϵ}(\cdot )$. We prove that for any relation $f \subseteq {0,1}^n \times $\mathcal{R}$$andBooleanfunction$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$istherelationobtainedbycomposing$f$and$g$\mathrm{.}Wealsoshowthat$R_{1/3}\left(f \circ \left(g^\oplus_{O(\log n)}\right)^n\right)=\Omega(\log n \cdot R_{4/9}(f) \cdot R_{1/3}(g))$,where$g^\oplus_{O(\log n)}$ is the function obtained by composing the xor function on $O(\log n)$ bits and $g^t$.