XOR Lemmas for Communication via Marginal Information

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.