期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2016
卷号：2016
页码：1-8
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：In this note, we study the relationship 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_k(x_1,\ldots, x_k) {\stackrel{{\mathsf{def}}}{=}} f(x_1\oplus\cdots\oplus x_k)$, denoted by ${\rm CC}^{(k)}(F_k )$. It is known that ${\rm CC}^{(k)}(F_k )\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)= O ({\rm CC}^{(4)}(F_k )^5 .\] Our main tool is a recent result from additive combinatorics due to Sanders. As ${\rm CC}^{(k)}(F_k )$ 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\geq 4$. Remark: After a first version of this paper was finished, we were informed that Hatami and Lovett had already discovered the same result a few years ago, without writing it up
关键词：Parity decision tree complexity; communication complexity; XOR;functions; Log-Rank Conjecture.
