ECCC-Report TR06-097https://eccc.weizmann.ac.il/report/2006/097Comments and Revisions published for TR06-097en-usWed, 16 Aug 2006 21:29:36 +0300
Paper TR06-097
| New correlation bounds for GF(2) polynomials using Gowers uniformity |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2006/097We study the correlation between low-degree GF(2) polynomials p and explicit functions. Our main results are the following:
(I) We prove that the Mod_m unction on n bits has correlation at most exp(-Omega(n/4^d)) with any GF(2) polynomial of degree d, for any fixed odd integer m. This improves on the previous exp(-Omega(n/8^d)) bound by Bourgain (C. R. Acad. Sci. Paris, 2005) and Green et al. (C. R. Acad. Sci. Paris, 2005).
(II) We exhibit a polynomial-time computable function on n bits that has correlation at most exp(-Omega(n/2^d)) with any GF(2) polynomial of degree d. Previous to our work the best correlation bound for an explicit function was exp(-Omega(n/(d 2^d))), which follows from (Chung and Tetali; SIAM J. Discrete Math., 1993).
(III) We derive an `XOR Lemma' for low-degree GF(2) polynomials: We show that if a function f has correlation at most 1-4^(-d) with any GF(2) polynomial of degree d (and Pr_x[f(x) = 1] ~ 1/2) then the XOR of m independent copies of f has correlation at most exp(-Omega(m/4^d)) with any GF(2) polynomial of degree d.
Our results rely on a measure of the `complexity' of a function due to Gowers (Geom. Funct. Anal., 1998 & 2001).
Wed, 16 Aug 2006 21:29:36 +0300https://eccc.weizmann.ac.il/report/2006/097