Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-124 | 3rd August 2020 21:36

A Strong XOR Lemma for Randomized Query Complexity

RSS-Feed




TR20-124
Authors: Joshua Brody, JaeTak Kim, Peem Lerdputtipongporn, Hariharan Srinivasulu
Publication: 17th August 2020 16:19
Downloads: 554
Keywords: 


Abstract:

We give a strong direct sum theorem for computing $XOR \circ g$. Specifically, we show that the randomized query complexity of computing the XOR of $k$ instances of $g$ satisfies $\bar{R}_\varepsilon(XOR \circ g)=\Theta(\bar{R}_{\varepsilon/k}(g))$. This matches the naive success amplification bound and answers a question of Blais and Brody.

As a consequence of our strong direct sum theorem, we give a total function $g$ for which $R(XOR \circ g) = \Theta(k\log(k)R(g))$, answering an open question from Ben-David et al.



ISSN 1433-8092 | Imprint