Theory of Computing ------------------- Title : Fourier Sparsity and Dimension Authors : Swagato Sanyal Volume : 15 Number : 11 Pages : 1-13 URL : https://theoryofcomputing.org/articles/v015a011 Abstract -------- We prove that the Fourier dimension of any Boolean function with Fourier sparsity $s$ is at most $O(\sqrt{s} \log s)$. 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).