Revised: August 19, 2019
Published: October 27, 2019
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).
Licensed under a Creative Commons Attribution License (CC-BY)