The correlation between parity and quadratic polynomials mod 3

摘要

We prove exponentially small upper bounds on the correlation between parity and quadratic polynomials mod3. One corollary of this is that in order to compute parity, circuits consisting of a threshold gate at the top, mod3 gates in the middle, and AND gates of fan-in two at the inputs must be of size 2Ω(n). This is the first result of this type for general mod3 subcircuits with ANDs of fan-in greater than 1. This yields an exponential improvement over a long-standing result of Smolensky, answering a question recently posed by Alon and Beigel. The proof uses a novel inductive estimate of the relevant exponential sums introduced by Cai, Green and Thierauf. The exponential sum and correlation bounds presented here are tight.