Volume 19 (2023) Article 9 pp. 1-35

Optimal Composition Theorem for Randomized Query Complexity

by Dmytro Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal

Received: January 11,2021
Revised: December 29, 2023
Published: December 30, 2023

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

DOI: 10.4086/toc.2023.v019a009

© 2023 Dmytro Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal
Licensed under a Creative Commons Attribution License (CC-BY)