A composition theorem for randomized query complexity via max conflict complexity

Let $R_{ϵ}(\cdot )$ stand for the bounded-error randomized query complexity with error $ϵ>0$. For any relation $f \subseteq {0,1}^n \times S$andpartialBooleanfunction$g \subseteq {0,1}^m \times {0,1}$, we show that $R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \sqrt{R_{1/3}(g)})$,where$f \circ g^n \subseteq ({0,1}^m)^n \times S$ is the composition of $f$ and $g$. We give an example of a relation $f$ and partial Boolean function $g$ for which this lower bound is tight. We prove our composition theorem by introducing a new complexity measure, the max conflict complexity $\bar{\chi }(g)$ of a partial Boolean function $g$. We show $\bar{\chi }(g)\in \mathrm{\Omega }(\sqrt{R_{1\mathrm{/}3}(g)})$ for any (partial) function $g$ and $R_{1\mathrm{/}3}(f\circ g^n)\in \mathrm{\Omega }(R_{4\mathrm{/}9}(f)\cdot \bar{\chi }(g))$; these two bounds imply our composition result. We further show that $\bar{\chi }(g)$ is always at least as large as the sabotage complexity of $g$, introduced by Ben-David and Kothari.