We show that degree-$d$ block-symmetric polynomials in
$n$ variables modulo any odd $p$ correlate with parity
exponentially better than degree-$d$ symmetric
polynomials, if $n \ge c d^2 \log d$ and $d \in [0.995
\cdot p^t - 1,p^t)$ for some $t \ge 1$. For these
infinitely many degrees, our result solves an open
problem raised by a number of researchers including Alon
and Beigel in 2001 \cite{AlB01}. The only previous case
for which this was known was $d=2$ and $p=3$
\cite{Gre04}.

The result is obtained through the development of a
theory we call \emph{spectral analysis of symmetric
correlation}, which originated in works of Cai, Green,
and Thierauf \cite{CaiGT96,Green99}. In particular, our
result follows from a detailed analysis of the
correlation of symmetric polynomials, which is determined
up to an exponentially small relative error when $d =
p^t-1$.

We give a partial complement to our result by showing
that for degree $d=p^t$, $p$ prime, block-symmetric
polynomials correlate exponentially worse than symmetric,
assuming that the blocks are large enough which is the
case above. Moreover we show the same holds for every $d$
in the case of polynomials modulo $p=2$ vs.~the Mod$_3$
function. In this setting we present computational
evidence that symmetric polynomials may in fact be
optimal.

This work builds on a study of correlation using computer
search by the authors which gave unexpected results. The
latter are here explained analytically. We advocate
further use of computer search in complexity theory.