Anti-Concentration for Polynomials of Independent Random Variables
summary
Gives an explicit anti‑concentration bound: for a degree‑d real polynomial whose rank = number of disjoint degree‑d monomials equals r, the mass on any single value (e.g. zero) is at most about Pr[p=0] = O~(r^{-1/(4d)}) (for constant d this matches roughly r^{-1/2}), with a lower‑bound obstruction of roughly e^{d}/√r. Proof translates the Boolean hypercube to Gaussians and uses the invariance principle. Applications include near‑optimal barriers for low‑degree polynomial approximation of parity and OR.
AI-written summary · about