ECCC-Report TR12-160https://eccc.weizmann.ac.il/report/2012/160Comments and Revisions published for TR12-160en-usTue, 20 Nov 2012 16:28:20 +0200
Paper TR12-160
| Block-symmetric polynomials correlate with parity better than symmetric |
Emanuele Viola,
Frederic Green,
Daniel Kreymer
https://eccc.weizmann.ac.il/report/2012/160
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.
Tue, 20 Nov 2012 16:28:20 +0200https://eccc.weizmann.ac.il/report/2012/160