  For any Boolean functions $f$ and $g$, the question whether $R(f\circ g) =
\tilde{\Theta}(R(f)R(g))$, is known as the composition question for the
randomized query complexity. Similarly, the composition question for the
approximate degree asks whether $\widetilde{deg}(f\circ g) =
\tilde{\Theta}(\widetilde{deg}(f)\cdot\widetilde{deg}(g))$. These questions are
two of the most important and well-studied problems, and yet we are far from
answering them satisfactorily.
  It is known that the measures compose if one assumes various properties of
the outer function $f$ (or inner function $g$). This paper extends the class of
outer functions for which $\text{R}$ and $\widetilde{\text{deg}}$ compose.
  A recent landmark result (Ben-David and Blais, 2020) showed that $R(f \circ
g) = \Omega(noisyR(f)\cdot R(g))$. This implies that composition holds whenever
$noisyR(f) = \Tilde{\Theta}(R(f))$. We show two results:
  (1)When $R(f) = \Theta(n)$, then $noisyR(f) = \Theta(R(f))$.
  (2) If $\text{R}$ composes with respect to an outer function, then
$\text{noisyR}$ also composes with respect to the same outer function. On the
other hand, no result of the type $\widetilde{deg}(f \circ g) = \Omega(M(f)
\cdot \widetilde{deg}(g))$ (for some non-trivial complexity measure $M(\cdot)$)
was known to the best of our knowledge. We prove that
  $\widetilde{deg}(f\circ g) = \widetilde{\Omega}(\sqrt{bs(f)} \cdot
\widetilde{deg}(g)),$
  where $bs(f)$ is the block sensitivity of $f$. This implies that
$\widetilde{\text{deg}}$ composes when $\widetilde{\text{deg}}(f)$ is
asymptotically equal to $\sqrt{\text{bs}(f)}$.
  It is already known that both $\text{R}$ and $\widetilde{\text{deg}}$ compose
when the outer function is symmetric. We also extend these results to weaker
notions of symmetry with respect to the outer function.

Computational Complexity