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

arXiv1204.0543MaRDI QIDQ6232052FDOQ6232052

Daniel M. Kane

Publication date: 2 April 2012

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,\mathrm{...},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),\mathrm{...},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.

Mathematics Subject Classification ID

Gaussian processes (60G15) Combinatorics in computer science (68R05)

This page was built for publication: A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6232052)