Title: New correlation bounds for GF(2) polynomials using the Gowers norm
Speaker: Emanuele Viola, IAS
Date: Wednesday, March 7, 2007 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In this work we study the correlation between low-degree GF(2) polynomials and explicit functions, where the correlation between f,p : {0,1}^n -> {+1,-1} is defined as Correlation(p,f) := | E_x [f(x) p(x)] | = | P_x[f(x) = p(x)] - P_x[f(x) != p(x)] |. Correlation bounds have applications to circuit lower bounds and pseudorandom generators, and are a fundamental benchmark for our understanding of complexity theory: Currently no explicit function on n bits is known to have negligible correlation with GF(2) polynomials of degree log_2 n.
In this work, for the first time, we apply the ``Gowers norm'' to the study of correlation bounds. In particular we obtain: (I) An `XOR Lemma' for low-degree polynomials: We show that if a function f has correlation at most .5 with any degree-d polynomial then f(x_1) f(x_2) ... f(x_m) has correlation at most exp(-m/4^d) with any degree-d polynomial. Previously such a result was not known for any degree d > 1. (II) A new proof that the Mod(3) function has correlation exp(-n/4^d) with any polynomial of degree d. Such a result was recently obtained in a breakthrough work by Bourgain (C. R. Acad. Sci. Paris, 2005). Our proof appears to be more modular and achieves a slightly better bound.
A write-up of these results is available at http://eccc.hpi-web.de/eccc-reports/2006/TR06-097/index.html. These results are part of a larger work which is joint with Avi Wigderson (to appear in CCC07).