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 \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 is the relation obtained by composing f and g. We also show using an XOR lemma that \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.

Corrected typos

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 \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 is the relation obtained by composing f and g. We also show that \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.