Theory of Computing
-------------------
Title : Anti-concentration for Polynomials of Independent Random Variables
Authors : Raghu Meka, Oanh Nguyen, and Van Vu
Volume : 12
Number : 11
Pages : 1-17
URL : http://www.theoryofcomputing.org/articles/v012a011
Abstract
--------
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.