[Colloquium] [Staff] CS Theory Seminar

[Donna Brooms]

REMINDER
 
Theory Seminar
 
Tuesday, March 18th
3:00 pm
Ryerson 276
 
Anindya De
Institute for Advanced Study in New Jersey
www.math.ias.edu/~anindya/
 
Title “Central limit theorem for Gaussian chaos, Polynomial decomposition and deterministic approximate counting for low-degree polynomial threshold functions.”
 
Abstract: The class of polynomial threshold functions (PTFs) is one of the most well-studied classes of Boolean functions in complexity theory and learning theory. The problem of deterministic approximate counting for polynomial threshold functions (over the Boolean hypercube) is an important problem in the area of unconditional derandomization and has been the subject of a lot of research in the past decade. Despite this, the problem of getting an algorithm with polynomial running time and sub-constant error has remained open. In this talk, we offer a positive resolution to this problem.
 
The novel ingredients in this work are:
(i) A new central limit theorem for low-degree polynomials of Gaussians. Roughly speaking, it states that a necessary and sufficient condition for the distribution of a low-degree Gaussian polynomial to be close to a Gaussian with the same mean and variance is that its (appropriately defined) eigenvalues are small. The proof uses the so-called Stein's method from probability theory and Malliavin calculus.
 
(ii) A new decomposition procedure which can express a given low-degree polynomial in terms of a few polynomials all of which have "small" eigenvalues. A novel feature of this lemma is that the number of polynomials and the bound on the eigenvalue can be essentially chosen to be free parameters at the cost of slightly perturbing the polynomial. This lemma is likely to be of independent interest and useful in other applications.
 
Joint work with Rocco Servedio.
 
Host: Prof. Alexander Razborov
Refreshments will be served prior to the talk in Ryerson 255 @ 2:30 pm