An XOR Lemma for Deterministic Communication Complexity

We prove a lower bound on the communication complexity of computing the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> -fold xor of an arbitrary function <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex>, in terms of the communication complexity and rank of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex>. We prove that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$D(f^{\oplus n}) \geq n\cdot(\frac{\Omega(D(f))}{\log \mathrm{r}\mathrm{k}(t)}-\log \text{rk}(f))$</tex>, where here <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$D(f), D(f^{\oplus n})$</tex> represent the deterministic communication complexity, and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\text{rk}(f)$</tex> is the rank of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f$</tex>. Our methods involve a new way to use information theory to reason about deterministic communication complexity.