Theory of Computing
-------------------
Title : A Strong XOR Lemma for Randomized Query Complexity
Authors : Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, and Hariharan Srinivasulu
Volume : 19
Number : 11
Pages : 1-14
URL : https://theoryofcomputing.org/articles/v019a011
Abstract
--------
We give a strong direct sum theorem for computing $XOR_k\circ g$,
the $XOR$ of $k$ instances of the partial Boolean function $g$.
Specifically, we show that for every $g$ and every $k\geq 2$,
the randomized query complexity of computing the $XOR$ of $k$
instances of $g$ satisfies ${\bar R}_\epsilon(XOR_k\circ g) =
\Theta(k{\bar R}_{\epsilon/k}(g))$, where ${\bar R}_\epsilon(f)$
denotes the expected number of queries made by the most efficient
randomized algorithm computing $f$ with $\epsilon$ error. This
matches the naive success amplification upper bound and answers
a conjecture of Blais and Brody (CCC'19).
As a consequence of our strong direct sum theorem, we give a total
function $g$ for which $R(XOR_k\circ g) = \Theta(k \log(k)\cdot R(g))$,
where $R(f)$ is the number of queries made by the most efficient
randomized algorithm computing $f$ with $1/3$ error. This answers
a question from Ben-David et al. (RANDOM'20).