Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR11-039 | 19th March 2011
Frederic Green, Daniel Kreymer, Emanuele Viola

In Brute-Force Search of Correlation Bounds for Polynomials

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

ISSN 1433-8092 | Imprint