Volume 15 (2019) Article 11 pp. 1-13
Fourier Sparsity and Dimension
Revised: August 19, 2019
Published: October 27, 2019
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.