Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



TR12-160 | 20th November 2012 16:28

Block-symmetric polynomials correlate with parity better than symmetric


Authors: Frederic Green, Daniel Kreymer, Emanuele Viola
Publication: 20th November 2012 16:28
Downloads: 854


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$

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 =

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

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.

ISSN 1433-8092 | Imprint