Let f:\0,1\ⁿ→\0,1\ be a boolean function. Its associated XOR function is the two-party function f⊕(x,y)=f(x⊕ y). We show that, up to polynomial factors, the deterministic communication complexity of f⊕ 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.
No takes yet. Share an insight, caveat, or question.
Hatami et al. (2018) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: