In this paper, we prove a strong XOR lemma for bounded-round two-player randomized communication. For a function $f:\mathcal{ X}\times \mathcal{ Y}\rightarrow\{ 0,1\}$, the $n$-fold XOR function $f^{ \oplus n}:\mathcal{ X}^n\times \mathcal{ Y}^n\rightarrow\{ 0,1\}$ maps $n$ input pairs $(X_1,\ldots,X_n,Y_1,\ldots,Y_n)$ to the XOR of the $n$ output bits $f(X_1,Y_1)\oplus \cdots \oplus f(X_n, Y_n)$. We prove that if every $r$-round communication protocols that computes $f$ with probability $2/3$ uses at least $C$ bits of communication, then any $r$-round protocol that computes $f^{ \oplus n}$ with probability $1/2+\exp(-O(n))$ must use $n\cdot \left(r^{ -O(r)}\cdot C-1\right)$ bits. When $r$ is a constant and $C$ is sufficiently large, this is $\Omega(n\cdot C)$ bits. It matches the communication cost and the success probability of the trivial protocol that computes the $n$ bits $f(X_i,Y_i)$ independently and outputs their XOR, up to a constant factor in $n$. A similar XOR lemma has been proved for $f$ whose communication lower bound can be obtained via bounding the discrepancy [Shaltiel'03]. By the equivalence between the discrepancy and the correlation with $2$-bit communication protocols [Viola-Wigderson'08], our new XOR lemma implies the previous result.
Categories: cs.CC