Estimation of certain exponential sums arising in complexity theory

It is shown that the correlation on {0, 1}(n) between parity and a polynomial p(x(1),...., x(n)) is an element of 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 -> infinity. An application to circuit complexity, from where the problem originates, is given. (c) 2005 Academie des sciences. Published by Elsevier SAS. All rights reserved.