### Revision(s):

__
Revision #1 to TR14-088 | 11th August 2014 19:31
__
#### Near-optimal Upper Bound on Fourier dimension of Boolean Functions in terms of Fourier sparsity

**Abstract:**
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.

**Changes to previous version:**
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.

### Paper:

__
TR14-088 | 13th July 2014 20:26
__

#### Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity

**Abstract:**
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.

### Comment(s):

__
Comment #1 to TR14-088 | 21st July 2014 09:11
__
#### Improvement

**Comment:**
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