# A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions

Shalev Ben-David, Eric Blais

November 2020
### Abstract

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

Publication

*Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science*