A Strong XOR Lemma for Randomized Query Complexity

Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn +1

We give a strong direct sum theorem for computing $xor\circ g$. Specifically, we show that for every function g and every $k\ge 2$, the randomized query complexity of computing t…