An XOR Lemma for Deterministic Communication Complexity

2024/07/01 by S. Purushothaman Iyer, Iyer, Siddharth, Anup Rao +1 · 1 citation
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Interconnection Networks and Systems #IoT and Edge/Fog Computing #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.2407.01802

openalex publication_date 2024/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove a lower bound on the communication complexity of computing the n-fold xor of an arbitrary function f, in terms of the communication complexity and rank of f. We prove that D(f^{⊕ n}) ≥ n ⋅ ((Ω(D(f)))/(log rk(f)) -log rk(f) ), where here D(f), D(f^{⊕ n}) represent the deterministic communication complexity, and rk(f) is the rank of f. Our methods involve a new way to use information theory to reason about deterministic communication complexity.

Cited by

• Space-Bounded Communication Complexity of Unitaries

Related

• Strong XOR Lemma for Information Complexity
• XOR Lemmas for Communication via Marginal Information
• Communication Complexities of XOR functions
• One-Way Communication Complexity of Partial XOR Functions
• The Corruption Bound, Log Rank, and Communication Complexity