We prove that the Fourier dimension of any Boolean function with Fourier sparsity s is at most O (s~(1/2) log s). This bound is tight up to a factor of 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(r~(1/2)logr), where r is the rank of its communication matrix.
展开▼
