ECCC-Report TR20-124https://eccc.weizmann.ac.il/report/2020/124Comments and Revisions published for TR20-124en-usMon, 17 Aug 2020 16:19:41 +0300
Paper TR20-124
| A Strong XOR Lemma for Randomized Query Complexity |
Joshua Brody,
JaeTak Kim,
Peem Lerdputtipongporn,
Hariharan Srinivasulu
https://eccc.weizmann.ac.il/report/2020/124We 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.Mon, 17 Aug 2020 16:19:41 +0300https://eccc.weizmann.ac.il/report/2020/124