On the Minimal Fourier Degree of Symmetric Boolean Functions
Amir Shpilka, Avishay Tal · 2011
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→ {0,1} there exists a set Ø ≠ S ⊂ [k] such that |S| = O(Γ(k) + √k), and f̂(S) ≠ 0, where Γ(m) ≤ m0.525is the largest gap between consecutive prime numbers in {1,..., 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. [JCSS, 2004]. Namely, we show that the running time of their algorithm is at most nO(k0.525)· poly(n · 2k,log · (1/δ)) where n is the number of variables, k is the size of the junta (i.e. number of relevant variables) and δ is the error probability. In particular, for k ≥ log(n)1/ (1-0-525)≈ log(n)2.1our analysis matches the lower bound 2k(up to polynomial factors). Our bound on the degree greatly improves the previous result of Kolountzakis et al. [Combinatorica, 2009] who proved that |S| = O(k/ log k).