pdf icon
Volume 15 (2019) Article 11 pp. 1-13
Fourier Sparsity and Dimension
Received: December 29, 2018
Revised: August 19, 2019
Published: October 27, 2019
Download article from ToC site:
[PDF (226K)] [PS (944K)] [Source ZIP]
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).