论文标题
强大的XOR引理，用于随机查询复杂性
A Strong XOR Lemma for Randomized Query Complexity
论文作者
论文摘要
我们为计算$ xor \ circ g $提供了强大的直接总和定理。具体来说，我们表明，对于每个函数g和每一个$ k \ geq 2 $，计算G的随机查询复杂性，k的k个实例的XOR满足$ \ overline {r} _ \ eps（xor \ circ g g）=θ（k \ edimelline {ryperline {r} {r} _ _ {\ eps/k}（g）（g）（g）（g）（g））$。这匹配了幼稚的成功放大上限，并回答了Blais和Brody的猜想（CCC19）。 由于我们的强直接总和定理，我们给出了一个总函数g，$ r（xor \ circ g）=θ（k \ log（k）\ cdot r（g））$，回答了Ben-David等人（Arxiv：Arxiv：2006.10957v1）的一个空旷问题。
We give a strong direct sum theorem for computing $xor \circ g$. Specifically, we show that for every function g and every $k\geq 2$, the randomized query complexity of computing the xor of k instances of g satisfies $\overline{R}_\eps(xor\circ g) = Θ(k \overline{R}_{\eps/k}(g))$. This matches the naive success amplification upper bound and answers a conjecture of Blais and Brody (CCC19). As a consequence of our strong direct sum theorem, we give a total function g for which $R(xor \circ g) = Θ(k \log(k)\cdot R(g))$, answering an open question from Ben-David et al.(arxiv:2006.10957v1).
