Revised: August 19, 2019

Published: October 27, 2019

**Keywords:**Boolean functions, Fourier analysis

**ACM Classification:**F.2.3

**AMS Classification:**68Q17

**Abstract:**
[Plain Text Version]

We prove that the Fourier dimension of any Boolean function with Fourier sparsity $s$ is at most $O\left(\sqrt{s} \log s\right)$. This bound is tight up to a factor of $O(\log s)$ since the Fourier dimension and sparsity of the address function are quadratically related. We obtain our result by bounding the non-adaptive parity decision tree complexity, which is known to be equivalent to the Fourier dimension. A consequence of our result is that any XOR function has a protocol of complexity $O(\sqrt{r} \log r)$ in the simultaneous communication model, where $r$ is the rank of its communication matrix.

-------------

A conference version of this paper appeared in the Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015).