It is a challenging open problem to prove exponential lower bounds on circuits consisting of a single threshold gate at the top, modulo gates in the middle layer, and small AND gates at the bottom. The background and motivation behind this problem will be reviewed in this talk. We also present new exponentially small upper bounds on the correlation between parity and quadratic polynomials modulo 3. One corollary of this is that in order to compute parity, circuits consisting of a threshold gate at the top, modulo 3 gates in the middle, and AND gates of fan-in two at the inputs must be of size . This is the first result of this type for general modulo subcircuits with ANDs of fan-in greater than 1. This yields an exponential improvement over a recent result of Alon and Beigel. The proof uses a novel inductive estimate of the relevant exponential sums introduced by Cai, Green and Thierauf. The exponential sum bounds are tight.

This result is to appear at Computational Complexity 2002.