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 upto a factor of $\log s$ as the Fourier dimension and sparsity of
the address function are quadratically related. We obtain
the bound by observing that the Fourier dimension of a Boolean
function is equivalent to its non-adaptive parity decision tree
complexity, and then bounding the latter.
Avishay Tal pointed out a sloppiness in the earlier analysis and observed that the earler upper bound of O(s^{2/3})on Fourier dimension can be improved to a unconditional near-optimal O(\sqrt{s} \log s). In this article we rectify that weakness and give a simplified proof of the above claim. Avishay Tal declined to be an author but we acknowledge him with gratitude.
We prove that the Fourier dimension of any Boolean function with
Fourier sparsity $s$ is at most $O\left(s^{2/3}\right)$. Our proof
method yields an improved bound of $\widetilde{O}(\sqrt{s})$
assuming a conjecture of Tsang~\etal~\cite{tsang}, that for every
Boolean function of sparsity $s$ there is an affine subspace of
$\mathbb{F}_2^n$ of co-dimension $O(\poly\log s)$ restricted to
which the function is constant. This conjectured bound is tight upto
poly-logarithmic factors as the Fourier dimension and sparsity of
the address function are quadratically separated. We obtain
these bounds by observing that the Fourier dimension of a Boolean
function is equivalent to its non-adaptive parity decision tree
complexity, and then bounding the latter.
Avishay Tal has observed a weakness in the current analysis of the non-adaptive parity decision tree procedure, and his ideas lead to a near-optimal $O(\sqrt{s} \log s)$ upper bound on Fourier dimension. We shall incorporate that in our article soon. Swagato
