Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
Volume 19 (2023) Article 11 pp. 1-14
A Strong XOR Lemma for Randomized Query Complexity
Received: August 3, 2020
Revised: December 30, 2023
Published: December 31, 2023
Download article from ToC site:
[PDF (326K)] [PS (1213K)] [Source ZIP]
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 XORkg, the XOR of k instances of the partial Boolean function g. Specifically, we show that for every g and every k2, the randomized query complexity of computing the XOR of k instances of g satisfies ˉRϵ(XORkg)=Θ(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(XORkg)=Θ(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).