2022/08/23 by Yu, Huacheng
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2208.11152
In this paper, we prove a strong XOR lemma for bounded-round two-player randomized communication. For a function f:X× Y→\0,1\, the n-fold XOR function f⊕ n:Xn× Yn→\0,1\ maps n input pairs (X1,…,Xn,Y1,…,Yn) to the XOR of the n output bits f(X1,Y1)⊕ ⋯ ⊕ f(Xn, Yn). We prove that if every r-round communication protocols that computes f with probability 2/3 uses at least C bits of communication, then any r-round protocol that computes f⊕ n with probability 1/2+exp(-O(n)) must use n⋅ (r-O(r)⋅ C-1) bits. When r is a constant and C is sufficiently large, this is Ω(n⋅ C) bits. It matches the communication cost and the success probability of the trivial protocol that computes the n bits f(Xi,Yi) independently and outputs their XOR, up to a constant factor in n. A similar XOR lemma has been proved for f whose communication lower bound can be obtained via bounding the discrepancy [Shaltiel'03]. By the equivalence between the discrepancy and the correlation with 2-bit communication protocols [Viola-Wigderson'08], our new XOR lemma implies the previous result.