Technical Report MSC-2012-04

TR#:MSC-2012-04
Class:MSC
Title: On The Minimal Fourier Degree of Symmetric Boolean Functions
Authors: Avishay Tal
Supervisors: Amir Shpilka
PDFMSC-2012-04.pdf
Abstract: 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) + sqrt(k)), and the S-fourier coefficient of f is non-zero, where Γ(m) ≤ m^0.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 n^(O(Γ(k) + sqrt(k))) * poly(n, 2^k, 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 2^k (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)).

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2012/MSC/MSC-2012-04), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2012
To the main CS technical reports page

Computer science department, Technion
admin