On the Fourier Spectrum of Symmetric Boolean Functions

  • Amir Shpilka | Technion

It is well-known that any Boolean function f:-1,+1n to -1,+1 can be written uniquely as a polynomial f(x) = sumS subset [n] fs prodi in S xi. The collection of coefficients (fS‘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 fS 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) m0.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.

发言人详细信息

Amir Shpilka is an associate professor of computer science at the Technion, currently on leave at Microsoft Research NE. He received his Ph.D. in 2001 under the supervision of Avi Wigderson at the Hebrew University. He spent his postdoc years at Weizmann, Harvard and MIT. His research area is computational complexity and he is mostly interested in studying arithmetic circuits and in understanding properties of polynomials.

接下来观看