Let f:\{0,1\}^n \to \{0,1\} be a boolean function. Its associated XOR function is the two-party function f_\oplus(x,y) = f(x \oplus y).
We show that, up to polynomial factors, the deterministic communication complexity of f_{\oplus} is equal to the parity decision tree complexity of f.
This relies on a novel technique of entropy reduction for protocols, combined with existing techniques in Fourier analysis and additive combinatorics.

Let f:\{0,1\}^n \to \{0,1\} be a boolean function. Its associated XOR function is the two-party function f_\oplus(x,y) = f(x \oplus y).
We show that, up to polynomial factors, the deterministic communication complexity of f_{\oplus} is equal to the parity decision tree complexity of f.
This relies on a novel technique of entropy reduction for protocols, combined with existing techniques in Fourier analysis and additive combinatorics.