Revised: December 29, 2023

Published: December 30, 2023

**Keywords:**query complexity, randomized decision tree, composed function, lower bound

**ACM Classification:**F.1.2, F.2.3

**AMS Classification:**68Q17, 68W20

**Abstract:**
[Plain Text Version]

For any relation $f \subseteq \{0,1\}^n \times S$ and any partial
Boolean function $g$ defined on a subset of $\{0,1\}^m$,
we show that
$$
\R_{1/3}(f \circ g^n) \in \Omega\left(\R_{4/9}(f) \cdot
\sqrt{\R_{1/3}(g)}\right),$$
where $\R_\epsilon(\cdot)$ stands for the
*bounded-error randomized query complexity*
with error at most $\epsilon$, and
$f \circ g^n \subseteq \left(\{0,1\}^m\right)^n \times S$
denotes the composition of $f$ with $n$ instances of $g$.

We show that the new composition theorem is *optimal*
for the general case of relational problems:
A relation $f_0$ and a partial Boolean function $g_0$ are
constructed, such that $\R_{4/9}(f_0)\in\Theta(\sqrt{n})$,
$\R_{1/3}(g_0)\in\Theta(n)$ and $\R_{1/3}(f_0\circ g_0^n)\in\Theta(n)$.

The theorem is proved via introducing a new complexity measure,
*max-conflict complexity*, denoted by ${\bar\chi}(\cdot)$.
Its investigation shows that
${\bar\chi}(g)\in\Omega(\sqrt{\R_{1/3}(g)})$ for any partial
Boolean function $g$ and
$\R_{1/3}(f \circ g^n)\in\Omega(\R_{4/9}(f)\cdot{\bar\chi}(g))$
for any relation $f$, which readily implies the composition statement.
It is further shown that ${\bar\chi}(g)$ is always at least as large as
the *sabotage complexity* of $g$ (introduced by Ben-David and
Kothari in 2016).

--------------------

A preliminary version of this paper appeared in the Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP'19).