Theory of Computing
-------------------
Title : Optimal Composition Theorem for Randomized Query Complexity
Authors : Dmytro Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal
Volume : 19
Number : 9
Pages : 1-35
URL : https://theoryofcomputing.org/articles/v019a009
Abstract
--------
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(R_{4/9}(f)\cdot\sqrt{R_{1/3}(g)}),
where \R_\epsilon(\cdot) stands for the _bounded-error
randomized query complexity_ with error at most \epsilon,
and f\circ g^n\subseteq (\{0,1\}^m)^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).