A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over $F_2$. We introduce a new technique to prove such correlation bounds with $F_2$ polynomials. Using this technique, we bound the correlation of an XOR of Majorities with constant degree polynomials. In fact, we prove a more general XOR lemma that extends to arbitrary resilient functions. We conjecture that the technique generalizes to higher degree polynomials as well.

A key ingredient in our new approach is a structural result about the Fourier spectrum of low degree polynomials over $F_2$. We show that for any n-variate polynomial $p$ over $F_2$ of degree at most $d$, there is a small set $S \subset [n]$ of variables, such that almost all of the Fourier mass of $p$ lies on Fourier coefficients that intersect with $S$. In fact our result is more general, and finds such a set $S$ for any low-dimensional subspace of polynomials. This generality is crucial in deriving the new XOR lemmas.