Next: Introduction

# A Degree-Decreasing Lemma for (MOD q - MOD p) Circuits

Vince Grolmusz

### Abstract:

Consider a circuit, where the inputs of the bottom gates are degree-d polynomials of the input variables (p, q are different primes). Using our main tool -- the Degree Decreasing Lemma -- we show that this circuit can be converted to a circuit with linear polynomials on the input-level with the price of increasing the size of the circuit. This result has numerous consequences: for the Constant Degree Hypothesis of Barrington, Straubing and Thérien [3], and generalizing the lower bound results of Yan and Parberry [21], Krause and Waack [13] and Krause and Pudlák [12]. Perhaps the most important application is an exponential lower bound for the size of circuits computing the n fan-in AND, where the input of each gate at the bottom is an arbitrary integer valued function of cn variables (c<1) plus an arbitrary linear function of n input variables. We believe that the Degree Decreasing Lemma becomes a standard tool in modular circuit theory.

Vince Grolmusz
1999-11-08