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.