Revised: December 30, 2023
Published: December 31, 2023
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).
Licensed under a Creative Commons Attribution License (CC-BY)