Communication Complexities of XOR functions

Yaoyun Shi, Zhiqiang Zhang

We call $F:\{0,1{\}}^n\times \{0,1{\}}^n\to \{0,1\}$ a symmetric XOR function if for a function $S:\{0,1,...,n\}\to \{0,1\}$, $F(x,y)=S(|x\oplus y|)$, for any $x,y\in \{0,1{\}}^n$…