A STRUCTURE THEOREM FOR POORLY ANTICONCENTRATED POLYNOMIALS OF GAUSSIANS AND APPLICATIONS TO THE STUDY OF POLYNOMIAL THRESHOLD FUNCTIONS
成果类型：
Article
署名作者：
Kane, Daniel
署名单位：
University of California System; University of California San Diego; University of California System; University of California San Diego
刊物名称：
ANNALS OF PROBABILITY
ISSN/ISSBN：
0091-1798
DOI：
10.1214/16-AOP1097
发表日期：
2017
页码：
1612-1679
关键词：
摘要：
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.