A structure theorem for poorly anticoncentrated polynomials of Gaussians and applications to the study of polynomial threshold functions (Q2012247)

In this paper, the low degree polynomials of Gaussian random variables are studied and a structural result for degree-\(d\) polynomials is proved. In particular, it is shown that any degree-\(d\) polynomial, \(p\) can be approximated by another polynomial, \(p_0\), which can be decomposed as some function of polynomials \(q_1, \ldots, q_m\) with \(q_i\) normalized and \(m=O_d(1)\), so that if \(X\) is a Gaussian random variable, the probability distribution on \(\left(q_1(X), \ldots, q_m(X)\right)\) does not have too much mass in any small box. Using this result, the improved versions of a number of results about polynomial threshold functions are proved, including producing better pseudorandom generators, obtaining a better invariance principle, and proving improved bounds on noise sensitivity. Using this result, a number of improved results about polynomial threshold functions are proved, including pseudorandom generators, invariance principle and noise sensitivity bounds.