We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions $f$ and $g$ such that $\mathrm{R}(f\circ g)\ll \mathrm{R}(f)\mathrm{R}(g)$ . In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of $f$ ). Second, we show that for all $f$ and $g,\ \mathrm{R}(f\circ g) = \Omega(\text{noisyR}(f)\ \mathrm{R}(g))$ , where $\text{noisyR}(f)$ is a measure describing the cost of computing $f$ on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure $M(\cdot)$ satisfying $\mathrm{R}(f\circ g)=\Omega(M(f)\mathrm{R}(g))$ for all $f$ and $g$ , it must hold that $\text{noisyR}(f)=\Omega(M(f))$ for all $f$ . We also give a clean characterization of the measure $\text{noisyR}(f)$ : it satisfies $\text{noisyR}(f)=\Theta(\mathrm{R}(f\circ\text{GapMaj}_{n})/\mathrm{R}(\text{GapMaj}_{n}))$ , where $n$ is the input size of $f$ and $\text{GapMaj}_{n}$ is the $\sqrt{n}$ -gap majority function on $n$ bits.