Block-symmetric polynomials correlate with parity better than symmetric.
Frederic Green, Daniel Kreymer, Emanuele Viola · 2012
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 ≥ cd2 log d and d ∈ [0.995 · pt − 1, pt) for some t ≥ 1. For these infinitely many degrees, our result solves an open problem raised by a number of researchers including Alon and Beigel in 2001 [AB01]. The only previous case for which this was known was d = 2 and p = 3 [Gre04]. The result is obtained through the development of a theory we call spectral analysis of symmetric correlation, which originated in works of Cai, Green, and Thierauf [CGT96, Gre99]. 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 = pt − 1. We give a partial complement to our result by showing that for degree d = pt, 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 Mod3 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.