pdf icon
Volume 12 (2016) Article 11 pp. 1-17
Anti-concentration for Polynomials of Independent Random Variables
Received: August 11, 2015
Revised: June 16, 2016
Published: August 25, 2016
Download article from ToC site:
[PDF (278K)]    [PS (1202K)]    [PS.GZ (317K)]
[Source ZIP]
Keywords: complexity theory, random polynomials, anti-concentration, parity, random graphs
ACM Classification: F.1.1, G.2.2
AMS Classification: 68Q05, 68R10

Abstract: [Plain Text Version]

We prove anti-concentration results for polynomials of independent random variables with arbitrary degree. Our results extend the classical Littlewood-Offord result for linear polynomials, and improve several earlier estimates.

We discuss applications in two different areas. In complexity theory, we prove near-optimal lower bounds for computing the PARITY function, addressing a challenge in complexity theory posed by Razborov and Viola, and also address a problem concerning the OR function. In random graph theory, we derive a general anti-concentration result on the number of copies of a fixed graph in a random graph.