next up previous
Next: Preliminaries Up: A Degree-Decreasing Lemma for Previous: A Degree-Decreasing Lemma for

Introduction

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 -- MODm gates are also allowed in the circuit? Here a MODm gate outputs 1 iff the sum of its inputs is in a set $A\subset \{0,1,2,\ldots,m-1\}$ modulo m. Razborov [15] showed that for computing MAJORITY with AND, OR, NOT and MOD2 gates, exponential size is needed with constant depth. This result was generalized by Smolensky [16] for MODp gates instead of MOD2 ones, where p denotes a prime. Very little is known, however, if both MODp and MODq 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 MOD6 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 MODp 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 GFp (see [16]). But depth-2 circuits with MOD2 and MOD3 gates, or MOD6 gates can compute the n-fan-in OR and AND functions [11], [3]. Consequently, these circuits are more powerful than circuits with MODp 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 MODm 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 (MODq, MODp) 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 up previous
Next: Preliminaries Up: A Degree-Decreasing Lemma for Previous: A Degree-Decreasing Lemma for
Vince Grolmusz
1999-11-08