A structure theorem for poorly anticoncentrated polynomials of Gaussians and applications to the study of polynomial threshold functions
type: Item
instance of: scholarly article
title: A structure theorem for poorly anticoncentrated polynomials of Gaussians and applications to the study of polynomial threshold functions
zbMATH Open document ID: 1377.60051
DOI: 10.1214/16-AOP1097
published in: The Annals of Probability
publication date: 2017-07-28T00:00:00Z
review text: 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.
reviewed by: Vakhtang V. Kvaratskhelia
Mathematics Subject Classification ID: 60G15
zbMATH DE Number: 6754782
zbMATH Keywords: polynomial decompositions
zbMATH Keywords: Gaussian chaos
zbMATH Keywords: anticoncentration
zbMATH Keywords: invariance principle
author: Daniel M. Kane
MaRDI profile type: Publication
full work available at URL: 16-aop1097
OpenAlex ID: W2614431701
description: scientific article; zbMATH DE number 6754782