Chicago Journal of Theoretical Computer Science

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.

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