摘要：We prove that the Fourier dimension of any Boolean function with Fourier
sparsity s is at most O(
√
slogs). This bound is tight up to a factor of O(logs) 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(
√
rlogr) in the simultaneous communication model, where
r is the rank of its communication matrix.
