One-Way Communication Complexity of Partial XOR Functions

Vladimir V. Podolskii, Dmitrii Sluch

Boolean function $F(x,y)$ for $x,y\in \{0,1{\}}^n$ is an XOR function if $F(x,y)=f(x\oplus y)$ for some function $f$ on $n$ input bits, where $\oplus$ is a bit-wise XOR. XOR functio…