A structure theorem for poorly anticoncentrated polynomials of Gaussians and applications to the study of polynomial threshold functions
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.
- Bounding the sensitivity of polynomial threshold functions
- The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions
- Average sensitivity and noise sensitivity of polynomial threshold functions
- A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
- Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
- A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
- Anti-concentration of polynomials: dimension-free covariance bounds and decay of Fourier coefficients
- Bounding the sensitivity of polynomial threshold functions
- Polynomial threshold functions, hyperplane arrangements, and random tensors
- Dimension Reduction for Polynomials over Gaussian Space and Applications
- Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
- The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions
- Resolution of the quadratic Littlewood-Offord problem
This page was built for publication: A structure theorem for poorly anticoncentrated polynomials of Gaussians 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 Q2012247)
