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.