Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed




Revision #1
Authors: Swagato Sanyal
Accepted on: 11th August 2014 19:32
Downloads: 655
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 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





TR14-088
Authors: Swagato Sanyal
Publication: 15th July 2014 16:13
Downloads: 948
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
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

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