Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

On the Minimal Fourier Degree of Symmetric Boolean Functions
event speaker icon
Avishay Tal (M.Sc. Thesis Seminar)
event date icon
Wednesday, 06.04.2011, 14:30
event location icon
Taub 601
event speaker icon
Advisor: Prof. Eyal Kushilevitz and Assoc. Prof. Amir Shpilka.
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).