[Colloquium] Theory Seminar Reminder

[Donna Brooms]

DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF CHICAGO
Date: Tuesday, April 19, 2011
Time: 3 p.m.
Place: Ryerson 251
----------------------------------------------
Speaker: Amir Shpilka
http://www.cs.technion.ac.il/~shpilka/
From: Technion and Microsoft Research
Title: On the Minimal Fourier Degree of Symmetric Boolean Functions                                                                             
Abstract: In this paper we give a new upper bound on the minimal degree of a nonzero Fourier coefficient in any non-linear symmetric Boolean function. Specifically, we prove that for every non-linear and symmetric f:{0,1}^k -> {0,1} there exists a nonempty set S such that |S|=O(\Gamma(n) + \sqrt{n}), and the Fourier coefficient f^(S) is not zero, where \Gamma(m)\le m^{0.525} is the largest gap between consecutive prime numbers in {1,...,m}. 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). In particular, for k \ge log(n)^{1/(1-0.525)} =~ log(n)^{2.1} our analysis matches known lower bounds (up to a polynomial overhead). Our bound on the degree greatly improves the previous result of Kolountzakis et al. (Combinatorica '09) who showed that |S|=O(k/log k).
This is a joint work with Avishay Tal.                                                                                                                                                                                                Host: Prof. Laszlo Babai                                                                                                                                                                                                      (Refreshments will be served prior to the talk in Ry. 255)                                                                                                                                                                                Persons who need assistance should call 773-702-6614

 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20110419/86bf56e0/attachment.htm