期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-9
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We give a strong direct sum theorem for computing XOR ◦g. Specifically, we show that for every function g and every k ≥ 2, the randomized query complexity of computing the XOR of k instances of g satisfies Rε(XOR ◦g) = Θ(kR ε k (g)). This matches the naive success amplification upper bound and answers a conjecture of Blais and Brody [7]. As a consequence of our strong direct sum theorem, we give a total function g for which R(XOR ◦g) = Θ(k log(k) · R(g)), answering an open question from Ben-David et al. [5].
