Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity

We prove that the Fourier dimension of any Boolean function with Fourier sparsity

$$s$$

s

is at most

$$O\left( \sqrt{s} \log s\right) $$

O

s

log

s

. This bound is tight up to a factor of

$$O(\log s)$$

O

(

log

s

)

as the Fourier dimension and sparsity of the addressing 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 XOR functions have a one way deterministic communication protocol of communication complexity

$$O(\sqrt{r} \log r)$$

O

(

r

log

r

)

, where

$$r$$

r

is the rank of its communication matrix.