  We study the fundamental challenge of exhibiting explicit functions that have
small correlation with low-degree polynomials over $\mathbb{F}_{2}$. Our main
contributions include:
  1. In STOC 2020, CHHLZ introduced a new technique to prove correlation
bounds. Using their technique they established new correlation bounds for
low-degree polynomials. They conjectured that their technique generalizes to
higher degree polynomials as well. We give a counterexample to their
conjecture, in fact ruling out weaker parameters and showing what they prove is
essentially the best possible.
  2. We propose a new approach for proving correlation bounds with the central
"mod functions", consisting of two steps: (I) the polynomials that maximize
correlation are symmetric and (II) symmetric polynomials have small
correlation. Contrary to related results in the literature, we conjecture that
(I) is true. We argue this approach is not affected by existing "barrier
results".
  3. We prove our conjecture for quadratic polynomials. Specifically, we
determine the maximum possible correlation between quadratic polynomials modulo
2 and the functions $(x_{1},\dots,x_{n})\to z^{\sum x_{i}}$ for any $z$ on the
complex unit circle; and show that it is achieved by symmetric polynomials. To
obtain our results we develop a new proof technique: we express correlation in
terms of directional derivatives and analyze it by slowly restricting the
direction.
  4. We make partial progress on the conjecture for cubic polynomials, in
particular proving tight correlation bounds for cubic polynomials whose
degree-3 part is symmetric.
