Strong XOR Lemma for Information Complexity

For any 0,1-valued function f, its n-folded XOR is the function f⊕ n where f⊕ n(X1, …, Xn) = f(X1) ⊕ ⋯ ⊕ f(Xn). Given a procedure for computing the function f, one can apply a “naive” approach to compute f⊕ n by computing each f(Xi) independently, followed by XORing the outputs. This approach uses n times the resources required for computing f. In this paper, we prove a strong XOR lemma for information complexity in the two-player randomized communication model: if computing f with an error probability of O(n−1) requires revealing I bits of information about the players’ inputs, then computing f⊕ n with a constant error requires revealing Ω(n) · (I − 1 − on(1)) bits of information about the players’ inputs. Our result demonstrates that the naive protocol for computing f⊕ n is both information-theoretically optimal and asymptotically tight in error trade-offs.