A STRUCTURE THEOREM FOR POORLY ANTICONCENTRATED POLYNOMIALS OF GAUSSIANS AND APPLICATIONS TO THE STUDY OF POLYNOMIAL THRESHOLD FUNCTIONS

作者：Kane Daniel^*

来源：Annals of Probability, 2017, 45(3): 1612-1679.

DOI：10.1214/16-AOP1097

• Polynomial decompositions
• Gaussian chaos
• anticoncentration
• invariance principle

We prove a structural result for degree-d polynomials. In particular, we show that any degree-d polynomial, p can be approximated by another polynomial, pp, which can be decomposed as some function of polynomials q1,...,qm with qi normalized and m = O-d(1), so that if X is a Gaussian random variable, the probability distribution on (qi (X),..,qm(X)) does not have too much mass in any small box.
Using this result, we prove improved versions of a number of results about polynomial threshold functions, including producing better pseudorandom generators, obtaining a better invariance principle, and proving improved bounds on noise sensitivity.

• 出版日期2017-5