Revised: December 30, 2023

Published: December 31, 2023

**Keywords:**lower bounds, query complexity, direct sum

**ACM Classification:**F.1.1, F.1.3

**AMS Classification:**68Q09, 68Q10, 68Q17

**Abstract:**
[Plain Text Version]

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