Theory of Computing
-------------------
Title     : Randomized Query Complexity of Sabotaged and Composed Functions
Authors   : Shalev Ben-David and Robin Kothari
Volume    : 14
Number    : 5
Pages     : 1-27
URL       : https://theoryofcomputing.org/articles/v014a005

Abstract
--------

We study the composition question for bounded-error randomized query
complexity: Is $R(f \circ g) = \Omega(R(f)R(g))$ for all Boolean
functions $f$ and $g$? We show that inserting a simple Boolean
function $h$, whose query complexity is only $\Theta(\log R(g))$, in
between $f$ and $g$ allows us to prove $R(f\circ h\circ g) =
\Omega(R(f)R(h)R(g))$.

We prove this using a new lower bound measure for randomized query
complexity we call randomized _sabotage complexity_, $RS(f)$.
Randomized sabotage complexity has several desirable properties, such
as a perfect composition theorem, $RS(f \circ g) \geq RS(f) RS(g)$,
and a composition theorem with randomized query complexity, 
$R(f\circ g) = \Omega(R(f)RS(g))$. It is also a quadratically tight
lower bound for total functions and can be quadratically superior to
the partition bound, the best known general lower bound for randomized
query complexity.

Using this technique we also show implications for lifting theorems in
communication complexity. We show that a general lifting theorem for
zero-error randomized protocols implies a general lifting theorem for
bounded-error protocols.



A conference version of this paper appeared in the Proceedings of the
43rd International Colloquium on Automata, Languages, and  Programming
(ICALP  2016).