Exponential Correlation Bounds for Polynomials

We prove that the XOR of $k$ majorities on disjoint blocks of $\mathrm{\ell }$ bits has correlation at most $(2d\mathrm{/}\sqrt{\mathrm{\ell }}{)}^k$ with every degree-$d$ polynomial over ${\mathbb{F}}_2$. By known techniques, this implies pseudorandom generators with polylogarithmic seed length for low-degree polynomials over ${\mathbb{F}}_2$ and for alternating circuits with parity gates.