All reports by Author Frederic Green:

__
TR12-160
| 20th November 2012
__

Frederic Green, Daniel Kreymer, Emanuele Viola#### Block-symmetric polynomials correlate with parity better than symmetric

__
TR11-039
| 19th March 2011
__

Frederic Green, Daniel Kreymer, Emanuele Viola#### In Brute-Force Search of Correlation Bounds for Polynomials

Frederic Green, Daniel Kreymer, Emanuele Viola

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 ...
more >>>

Frederic Green, Daniel Kreymer, Emanuele Viola

We report on some initial results of a brute-force search for determining the maximum correlation between degree-$d$ polynomials modulo $p$ and the $n$-bit mod $q$ function. For various settings of the parameters $n,d,p,$ and $q$, our results indicate that symmetric polynomials yield the maximum correlation. This contrasts with the previously-analyzed ... more >>>