Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### 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

Revision #1
Authors: Swagato Sanyal
Accepted on: 11th August 2014 19:32
Keywords:

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 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

TR14-088
Authors: Swagato Sanyal
Publication: 15th July 2014 16:13
Keywords:

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
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

Authors: Swagato Sanyal
Accepted on: 21st July 2014 09:11
Keywords:

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

ISSN 1433-8092 | Imprint