2023/12/05 by Siddharth Iyer, Iyer, Siddharth, Anup Rao +1
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2312.03076
openalex publication_date 2023/12/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We define the marginal information of a communication protocol, and use it to prove XOR lemmas for communication complexity. We show that if every C-bit protocol has bounded advantage for computing a Boolean function f, then every Ω(C √(n))-bit protocol has advantage exp(-Ω(n)) for computing the n-fold xor f⊕ n. We prove exponentially small bounds in the average case setting, and near optimal bounds for product distributions and for bounded-round protocols.