A structure theorem for poorly anticoncentrated polynomials of Gaussians and applications to the study of polynomial threshold functions (Q2012247)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A structure theorem for poorly anticoncentrated polynomials of Gaussians and applications to the study of polynomial threshold functions |
scientific article |
Statements
A structure theorem for poorly anticoncentrated polynomials of Gaussians and applications to the study of polynomial threshold functions (English)
0 references
28 July 2017
0 references
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.
0 references
polynomial decompositions
0 references
Gaussian chaos
0 references
anticoncentration
0 references
invariance principle
0 references