Estimation of certain exponential sums arising in complexity theory
Jean Bourgain · Comptes Rendus Mathématique · 2005
It is shown that the correlation on { 0 , 1 } n between parity and a polynomial p ( x 1 , … , x n ) ∈ Z [ X 1 , … , X n ] ( mod q ) , q a fixed odd number and p ( X ) of degree d arbitrary but fixed, is exponentially small in n as n → ∞ . An application to circuit complexity, from where the problem originates, is given.