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.