We show that degree-d block-symmetric polynomials inn variables modulo any odd p correlate with parityexponentially better than degree-d symmetricpolynomials, if ncd2logd and d[0995pt−1pt) for some t1. For theseinfinitely many degrees, our result solves an openproblem raised by a number of researchers including Alonand Beigel in 2001 \cite{AlB01}. The only previous casefor which this was known was d=2 and p=3\cite{Gre04}.

The result is obtained through the development of atheory we call \emph{spectral analysis of symmetriccorrelation}, which originated in works of Cai, Green,and Thierauf \cite{CaiGT96,Green99}. In particular, ourresult follows from a detailed analysis of thecorrelation of symmetric polynomials, which is determinedup to an exponentially small relative error when d=pt−1.

We give a partial complement to our result by showingthat for degree d=pt, p prime, block-symmetricpolynomials correlate exponentially worse than symmetric,assuming that the blocks are large enough which is thecase above. Moreover we show the same holds for every din the case of polynomials modulo p=2 vs.~the Mod3function. In this setting we present computationalevidence that symmetric polynomials may in fact beoptimal.

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