Computer Science/Discrete Mathematics Seminar I

It is well-known that any Boolean function f:{-1,+1}^n \to {-1,+1} can be written uniquely as a polynomial f(x) = \sum_{S subset [n]} f_s \prod_{i in S} x_i. The collection of coefficients (f_S's) this expression are referred to (with good reason) as the Fourier spectrum of f. The Fourier spectrum has played a central role in modern computer science by converting combinatorial and algorithmic questions about f into algebraic or analytic questions about the spectrum. In this talk I will focus on a basic feature of the Fourier spectrum, namely the minimal Fourier degree, or the size of the smallest non-empty set S such that f_S is non-zero. For every symmetric function *except the parity function* we show that the minimal Fourier degree is at most O(Gamma(n)) where Gamma(m) < m^{0.525} is the largest gap between consecutive prime numbers in {1,...,m}. This improves the previous result of Kolountzakis et al. (Combinatorica '09) who showed that the minimal Fourier degree is at most k/log k. As an application we obtain a new analysis of the PAC learning algorithm for symmetric juntas, under the uniform distribution, of Mossel et al. (STOC '03). This is a joint work with Avishay Tal.