Exponential Size Lower Bounds for Some Depth 3 Circuits

AbstractExponential size lower bounds are obtained for some depth three circuits computing conjunction using one layer each of gates which compute Boolean functions of low total degree when expressed as polynomials, parity modulo-2 gates, and parity-modulo-q gates, where q is prime. One of these results implies a special case of the constant degree hypothesis of Barrington et al. The lower bounds are obtained from an algebraic characterization of the functions computed by the circuits: it is shown that certain integer multiples of these functions can be expressed 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 constant degree hypothesis