** Next:** Preliminaries
** Up:** A Degree-Decreasing Lemma for
** Previous:** A Degree-Decreasing Lemma for

Boolean circuits are one of the most interesting models of computation. They are widely examined in VLSI design, in general computability theory and in complexity theory context as well as in the theory of parallel computation.
Almost all of the strongest and deepest lower bound results for the computational complexity of finite functions were proved using the Boolean circuit model of computation ([14], [22], [10], [15], [16], or see [20] for a survey).
Even these famous and sophisticated lower bound results were proven for very restricted circuit classes.
Bounded depth and polynomial size is one of the most natural restrictions. Ajtai [1], Furst, Saxe, and Sipser [6] proved that no polynomial sized, constant depth circuit can compute the PARITY function. Yao [22] and Hstad [10] generalized this result for sub-logarithmic depths.
Since the modular gates are very simple to define, and they are immune to the random restriction techniques in lower bound proofs for the PARITY function, the following natural question was asked by several researchers: How powerful will become the Boolean circuits if -- beside the standard AND, OR and NOT gates -- MOD_{m} gates are also allowed in the circuit? Here a MOD_{m} gate outputs 1 iff the sum of its inputs is in a set
modulo *m*.
Razborov [15] showed that for computing MAJORITY with AND, OR, NOT and MOD_{2} gates, exponential size is needed with constant depth. This result was generalized by Smolensky [16] for MOD_{p} gates instead of MOD_{2} ones, where *p* denotes a prime.
Very little is known, however, if both MOD_{p} and MOD_{q} gates are allowed in the circuit for different primes *p*,*q*, or, if the modulus is a non-prime power composite, e.g., 6. For example, it is consistent with our present knowledge that depth-3, linear-size circuits with MOD_{6} gates *only*, recognize the Hamiltonian graphs (see [3]). The existing lower bound results use diverse techniques from Fourier-analysis, communication complexity theory, group-theory and several forms of random restrictions (see [3], [12], [18], [19], [17], [9], [7], [8], [2], [11]).
It is not difficult to see that constant-depth circuits with MOD_{p} gates only, (*p* prime), cannot compute even simple functions: the n-fan-in OR or AND functions, since they can only compute constant degree polynomials of the input variables over GF_{p} (see [16]).
But depth-2 circuits with MOD_{2} and MOD_{3} gates, or MOD_{6} gates can compute the *n*-fan-in OR and AND functions [11], [3]. Consequently, these circuits are more powerful than circuits with MOD_{p} gates only.
By the famous theorem of Yao [23] and Beigel and Tarui [4], every polynomial-size, constant-depth circuit with AND, OR, NOT and MOD_{m} gates can be converted to a depth-2 circuit with a SYMMETRIC gate at the top and quasi-polynomially many AND gates of poly-logarithmic fan-in at the bottom. This result would allow an excellent tool for bounding the power of circuits containing modular gates. Unfortunately, the existing lower bound techniques are not strong enough to bound the computational power of these circuits.
Our main contribution here is a lemma, the Degree Decreasing Lemma, which yields a tool for dealing with low-fan-in AND gates at the bottom of (MOD_{q}, MOD_{p}) circuits. We believe that - in the light of the result of Yao, Beigel and Tarui - our result may have further important consequences in modular circuit theory.

** Next:** Preliminaries
** Up:** A Degree-Decreasing Lemma for
** Previous:** A Degree-Decreasing Lemma for
*Vince Grolmusz*

*1999-11-08*