Computer Science/Discrete Mathematics Seminar I

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

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.

Date & Time

February 14, 2011 | 11:15am – 12:15pm

Location

S-101

Affiliation

Member, School of Mathematics