Theory of Computing
-------------------
Title : Fourier Sparsity and Dimension
Authors : Swagato Sanyal
Volume : 15
Number : 11
Pages : 1-13
URL : http://www.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).