Abstract
We prove a lower bound on the communication complexity of computing the n -fold xor of an arbitrary function f , in terms of the communication complexity and rank of f . We prove that D(f^{\oplus n}) \geq n\cdot(\frac{\Omega(D(f))}{\log \mathrm{r}\mathrm{k}(t)}-\log \text{rk}(f)) , where here D(f), D(f^{\oplus n}) represent the deterministic communication complexity, and \text{rk}(f) is the rank of f . Our methods involve a new way to use information theory to reason about deterministic communication complexity.