COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR I | |

Topic: | On the Fourier Spectrum of Symmetric Boolean Functions |

Speaker: | Amir Shpilka |

Affiliation: | Technion; on leave at Microsoft Research New England |

Date: | Monday, March 14 |

Time/Room: | 11:15am - 12:15pm/S-101 |

Video Link: | https://video.ias.edu/csdm/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). This is a joint work with Avishay Tal.