#

### Volume 2016

#### Article 12

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

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

Penghui Yao

Centrum Wiskunde & Informatica

Amsterdam, Holland.

`phyao1985 AT gmail DOT com`

August 20, 2016
#### 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.