Parity Decision Tree Complexity and 4-Party Communication Complexity of XOR-functions Are Polynomially Equivalent

In this note, we study the relation between the parity decision tree complexity of a boolean function $f$, denoted by ${\mathrm{D}}_{\oplus }(f)$, and the $k$-party number-in-hand multiparty communication complexity of the XOR functions $F(x_1,\dots ,x_k)=f(x_1\oplus \cdots \oplus x_k)$, denoted by ${\mathrm{C}\mathrm{C}}^{(k)}(F)$. It is known that $$\mathrm{C}\mathrm{C}$^{(k)}(F)\leq k\cdot$\mathrm{D}$_{\oplus}(f)$ because the players can simulate the parity decision tree that computes $f$. In this note, we show that $${\mathrm{D}}_{\oplus }(f)\le O({\mathrm{C}\mathrm{C}}^{(4)}(F{)}^5)\mathrm{.}$$ Our main tool is a recent result from additive combinatorics due to Sanders. As ${\mathrm{C}\mathrm{C}}^{(k)}(F)$ is non-decreasing as $k$ grows, the parity decision tree complexity of $f$ and the communication complexity of the corresponding $k$-argument XOR functions are polynomially equivalent whenever $k\ge 4$. Remark: After the first version of this paper was finished, we discovered that Hatami and Lovett had already discovered the same result a few years ago, without writing it up.