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 : https://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.