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