M.Sc Thesis | |
M.Sc Student | Tal Avishay |
---|---|
Subject | On The Minimal Fourier Degree of Symmetric Boolean Functions |
Department | Department of Computer Science | Supervisor | ASSOCIATE PROF. Amir Shpilka |
Full Thesis text | ![]() |
In this thesis 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 non-empty subset S of {1,...,n} such that |S| = O(Γ(k) √k), and the S-fourier coefficient of f is non-zero, where Γ(m) ≤ m0.525 is 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. [MOS04]. Namely, we show that the running time of their algorithm is at most nO(Γ(k) √k) 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.1 our analysis matches the lower bound 2k (up to polynomial factors).
Our bound on the degree greatly improves the previous result of Kolountzakis et al. [KLMMV09] who proved that |S| = O(k / log(k)).