pdf icon
Volume 19 (2023) Article 9 pp. 1-35
Optimal Composition Theorem for Randomized Query Complexity
Received: January 11,2021
Revised: December 29, 2023
Published: December 30, 2023
Download article from ToC site:
[PDF (481K)] [PS (2466K)] [Source ZIP]
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]

$ \newcommand{\R}{{\mathbb R}} \newcommand{\dr}{\nicefrac} \newcommand{\sq}{\sqrt} \newcommand{\asT}[1]{\Theta(#1)} \newcommand{\e}{\emph} \newcommand{\ccc}{max-conflict complexity} $

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).