XOR Lemmas for Communication via Marginal Information

We define the $\mathit{\text{marginal}}\mathit{\text{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 $\tilde{\mathrm{\Omega }}(C\sqrt{n})$-bit protocol has advantage $\exp (-\mathrm{\Omega }(n))$ for computing the $n$-fold xor $f^{\oplus n}$. We prove exponentially small bounds in the average case setting, and near optimal bounds for product distributions and for bounded-round protocols.