ECCC-Report TR14-088https://eccc.weizmann.ac.il/report/2014/088Comments and Revisions published for TR14-088en-usMon, 11 Aug 2014 19:32:01 +0300
Revision 1
| Near-optimal Upper Bound on Fourier dimension of Boolean Functions in terms of Fourier sparsity |
Swagato Sanyal
https://eccc.weizmann.ac.il/report/2014/088#revision1 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.Mon, 11 Aug 2014 19:32:01 +0300https://eccc.weizmann.ac.il/report/2014/088#revision1
Comment 1
| Improvement |
Swagato Sanyal
https://eccc.weizmann.ac.il/report/2014/088#comment1Avishay 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. SwagatoMon, 21 Jul 2014 09:11:21 +0300https://eccc.weizmann.ac.il/report/2014/088#comment1
Paper TR14-088
| Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity |
Swagato Sanyal
https://eccc.weizmann.ac.il/report/2014/088We 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.Tue, 15 Jul 2014 16:13:46 +0300https://eccc.weizmann.ac.il/report/2014/088