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 <i>optimal</i> 
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).