ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-039 | 19th March 2011 21:15

In Brute-Force Search of Correlation Bounds for Polynomials

RSS-Feed




TR11-039
Authors: Frederic Green, Daniel Kreymer, Emanuele Viola
Publication: 19th March 2011 21:15
Downloads: 761
Keywords: 


Abstract:

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 settings of parameters, where non-symmetric polynomials yield the maximum correlation.

We also prove new properties of maximum-correlation polynomials, and use those to obtain a new setting of parameters where those polynomials are not symmetric.



ISSN 1433-8092 | Imprint