Title: Central Limit Theorem for Gaussian Chaos and Deterministic Counting for Polynomial Threshold Functions
Speaker: Anindya De, IAS
Date: Wednesday, March 5, 2014 11:00-12:00pm
Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
It is a well-known fact that linear combinations of Gaussians are Gaussians. What about polynomial combinations? In this talk, we will see a new central limit theorem for polynomials of Gaussians. The techniques will draw from the so-called "Stein's method" in probability theory and Malliavin calculus. As the main application, we will give the first deterministic polynomial time algorithm for approximate counting of any constant degree PTF with subconstant error. This theorem will involve a new decomposition procedure for polynomial which might be of interest in other applications as well.
Joint work with Rocco Servedio.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/