Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-178 | 17th November 2010 18:58

On the Minimal Fourier Degree of Symmetric Boolean Functions


Authors: Amir Shpilka, Avishay Tal
Publication: 17th November 2010 18:58
Downloads: 3297


In this paper we give a new upper bound on the minimal degree of a nonzero Fourier coefficient in any non-linear symmetric Boolean function.
Specifically, we prove that for every non-linear and symmetric $f:\{0,1\}^{k} \to \{0,1\}$ there exists a set $\emptyset\neq S\subset[k]$ such that $|S|=O(\Gamma(k)+\sqrt{k})$, and $\hat{f}(S) \neq 0$, where $\Gamma(m) \leq m^{0.525}$ is the largest gap between consecutive prime numbers in $\{1,\ldots,m\}$.
As an application we obtain a new analysis of the PAC learning algorithm for symmetric juntas, under the uniform distribution, of Mossel et al. Namely, we show that the running time of their algorithm is at most $n^{O(k^{0.525})} \cdot \mathrm{poly}(n,2^{k},\log(1/\delta))$ where $n$ is the number of variables, $k$ is the size of the junta (i.e. number of relevant variables) and $\delta$ is the error probability. In particular, for $k\geq\log(n)^{1/(1-0.525)}\approx \log(n)^{2.1}$ our analysis matches the lower bound $2^k$ (up to polynomial factors).

Our bound on the degree greatly improves the previous result of Kolountzakis et al. who proved that $|S|=O(k/\log k)$.

ISSN 1433-8092 | Imprint