Given a boolean function $f : \{0, 1\}^n \rightarrow \{0, 1\}$ define the function $f \circ \mathsf{XOR}$ on $2n$ bits by $f \circ \mathsf{XOR} (x_1, \dots, x_n, y_1, \dots, y_n) = f(x_1 \oplus y_1, \dots, x_n \oplus y_n)$. Such a function is called an $\mathsf{XOR}$ function. A natural communication game for such a function is as follows. Alice is given $x = (x_1, \dots, x_n)$, Bob is given $y = (y_1, \dots, y_n)$, and they jointly wish to compute $f \circ \mathsf{XOR}(x, y)$. They have unbounded computational power individually and wish to minimize the amount of communication between them on the worst case input.
We study the communication complexity of $\mathsf{XOR}$ functions under various randomized models, and resolve several open questions in the areas of communication complexity, boolean circuit complexity and analysis of boolean functions.
1) We characterize the weakly-unbounded error communication complexity of $\mathsf{XOR}$ functions in terms on a certain approximation theoretic property of the outer function. We use this characterization to reprove several known results. Along the way, we also resolve some open questions in the area of analysis of boolean functions.
2) We prove a strong unbounded error communication complexity lower bound for an easily describable function. We then use this to show a boolean circuit complexity class separation that has been open since the early 90's, and first explicitly posed in 2005. This also resolves a recent open problem in communication complexity by separating two communication complexity classes.
We also prove lower bounds against the class of functions efficiently computable by decision lists of linear threshold functions, and prove unbounded error communication complexity lower bounds for $\mathsf{XOR}$ functions when the outer function is symmetric.
3) Finally, we separate two randomized communication complexity classes in the "number on forehead" model of multiparty communication. This also implies boolean circuit class separations.
