
Speaker Amir Shpilka Affiliation Technion Host Madhu Sudan Duration 01:12:26 Date recorded 23 February 2011 It is wellknown 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 nonempty set S such that f_{S} is nonzero. 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.
©2011 Microsoft Corporation. All rights reserved.
