  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 $R(f\circ
g)\ll R(f) 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$, $R(f\circ
g)=\Omega(\mathop{noisyR}(f)\cdot R(g))$, where $\mathop{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 $R(f\circ g)=\Omega(M(f)R(g))$ for all $f$ and
$g$, it must hold that $\mathop{noisyR}(f)=\Omega(M(f))$ for all $f$. We also
give a clean characterization of the measure $\mathop{noisyR}(f)$: it satisfies
$\mathop{noisyR}(f)=\Theta(R(f\circ gapmaj_n)/R(gapmaj_n))$, where $n$ is the
input size of $f$ and $gapmaj_n$ is the $\sqrt{n}$-gap majority function on $n$
bits.
