(MOD q - MOD p) Circuits

**Vince Grolmusz
**

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.

- Introduction
- Preliminaries
- The Degree-Decreasing Lemma
- Applications of the Degree Decreasing Lemma
- Bibliography
- About this document ...