next up previous
Next: Introduction

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

Vince Grolmusz
{Department of Computer Science, E\uml otv\uml os University, Bu...
...alborg, Denmark, published by Springer Verlag in the LNCS series.}


Consider a $(\hbox{\rm MOD}_q,\hbox{\rm MOD}_p)$ circuit, where the inputs of the bottom $\hbox{\rm MOD}_p$ 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 $(\hbox{\rm MOD}_q,\hbox{\rm MOD}_p)$ 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 $(\hbox{\rm MOD}_q,\hbox{\rm MOD}_p)$ circuits computing the n fan-in AND, where the input of each $\hbox{\rm MOD}_p$ 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