2020/07/10 by Brody, Joshua, Kim, Jae Tak, Lerdputtipongporn, Peem +1
#Computational Complexity (cs.CC) #F.1.2 #F.1.3 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2007.05580
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_\eps(xor∘ g) = Θ(k 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 ∘ g) = Θ(k log(k)⋅ R(g)), answering an open question from Ben-David et al.(arxiv:2006.10957v1).