2024/11/20 by Pachara Sawettamalya, Sawettamalya, Pachara, Huacheng Yu +1
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT) #Neural Networks and Applications #Quantum Computing Algorithms and Architecture #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2411.13015
openalex publication_date 2024/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.