Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-182 | 26th November 2010 05:42

An elementary proof of anti-concentration of polynomials in Gaussian variables


Authors: Shachar Lovett
Publication: 27th November 2010 04:29
Downloads: 4136


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.

ISSN 1433-8092 | Imprint