A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions

Daniel M. Kane

paper

A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions

arXiv:1204.0543

Abstract

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, $p_{0}$ , which can be decomposed as some function of polynomials $q_{1}, ..., q_{m}$ with $q_{i}$ normalized and $m = O_{d} (1)$ , so that if $X$ is a Gaussian random variable, the probability distribution on $(q_{1} (X), ..., q_{m} (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.

A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions

Abstract

Cited by in corpus (2)