An Elementary Proof of Anti-Concentration of Polynomials in Gaussian Variables

COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR I
Topic:An Elementary Proof of Anti-Concentration of Polynomials in Gaussian Variables
Speaker:Shachar Lovett
Affiliation:Member, School of Mathematics
Date:Monday, February 14
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/lovett3

Recently there has been much interest in polynomial threshold functions in the context of learning theory, structural results and pseudorandomness. A crucial ingredient in these works is the understanding of the distribution of low-degree multivariate polynomials evaluated over normally distributed inputs. In particular, the two important properties are exponential tail decay and anti-concentration. In this work we study the latter property. The important work in this area is by Carbery and Wright, who gave a tight bound for anti-concentration of polynomials in normal variables. However, the proof of their result is quite complex. We give a weaker anti-concentration result which has an elementary proof, based on some convexity arguments, simple analysis and induction on the degree. Moreover, our proof technique is robust and extends to other distributions.