Published by the Department of Computer Science, The University of Chicago.

Abstract

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.

• The article: PDF (417 KB)
• Source material: ZIP (81 KB)
• BibTeX entry for this article (356 bytes)

Submitted June 18, 2015, revised August 18, 2016, published August 20, 2016.

DOI: 10.4086/cjtcs.2016.012
© Penghui Yao
Licensed under a Creative Commons Attribution License




---

Volume 2016, Article 11
Volume 2016 Published articles