New correlation bounds for GF(2) polynomials using Gowers uniformity
Emanuele Viola · 2006
We study the correlation between low-degree GF (2) polynomials p and explicit functions. Our main results are the following: I We prove that theModm function on n bits has correlation at most exp (−Ω (n/4d)) with any GF (2) polynomial of degree d, for any fixed odd integer m. This im-proves on the previous exp (−Ω (n/8d)) 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 (−Ω (n/2d)) with any GF (2) polynomial of degree d. Previous to our work the best correlation bound for an explicit function was exp (−Ω (n / (d · 2d))), 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 Prx[f(x) = 1] ≈ 1/2) then the XOR of m independent copies of f has correlation at most exp (−Ω (m/4d)) with any GF (2) polynomial of degree d. Our results rely on a measure of the ‘complexity ’ of a function due to Gowers (Geom.