EXPONENTIAL SIZE LOWER BOUNDS FOR SOME DEPTH 3 CIRCUITS

Exponential size lower bounds are obtained for some depth three circui ts computing conjunction using one layer each of gates which compute B oolean functions of low total degree when expressed as polynomials, pa rity modulo-2 gates, and parity-modulo-q gates, where q is prime. One of these results implies a special case of the constant degree hypothe sis of Barrington et al. The lower bounds are obtained from an algebra ic characterization of the functions computed by the circuits: it is s hown that certain integer multiples of these functions can be expresse d as the sum of a lattice element and a function of small value. It is conjectured that this characterization can be used to resolve the con stant degree hypothesis. (C) 1994 Academic Press, Inc.