Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-097 | 9th August 2006 00:00

New correlation bounds for GF(2) polynomials using Gowers uniformity


Authors: Emanuele Viola
Publication: 16th August 2006 21:29
Downloads: 3530


We 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).

ISSN 1433-8092 | Imprint