TR12-160 Authors: Frederic Green, Daniel Kreymer, Emanuele Viola

Publication: 20th November 2012 16:28

Downloads: 1846

Keywords:

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.