Revised: December 30, 2023
Published: December 31, 2023
Abstract: [Plain Text Version]
We give a strong direct sum theorem for computing XORk∘g, the XOR of k instances of the partial Boolean function g. Specifically, we show that for every g and every k≥2, the randomized query complexity of computing the XOR of k instances of g satisfies ˉRϵ(XORk∘g)=Θ(kˉRϵ/k(g)), where ˉRϵ(f) denotes the expected number of queries made by the most efficient randomized algorithm computing f with ϵ 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(XORk∘g)=Θ(klog(k)⋅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).