next up previous
Next: The ID function Up: Applications of the Degree Previous: Applications of the Degree

Constant Degree Hypothesis

Barrington, Straubing and Thérien in [3] conjectured that any $(\hbox{\rm MOD}^B_q,\hbox{\rm MOD}^A_p; d)$ circuit needs exponential size to compute the n fan-in AND function. They called it the Constant Degree Hypothesis (CDH), and proved the d=1 case, with group-theoretic techniques. Yan and Parberry [21] - using Fourier-analysis - proved also the d=1 case for $(\hbox{\rm MOD}^{\{1,2,\ldots,q-1\}}_q,\hbox{\rm MOD}^{\{1\}}_2; 1)$ circuits, but their method also works for the special case of the CDH where the sum of the degrees of the monomials gi on the input-level satisfies:

\begin{displaymath}\sum_{\deg(g_i)\geq 1}(\deg(g_i)-1)\leq \frac{n}{2(q-1)}-O(1).\end{displaymath}

Our Theorem 9 yields the following generalization of this result:

Theorem 5   There exist 0<c<1 and 0<c'<1, such that if a $(\hbox{\rm MOD}^B_q, \hbox{\rm MOD}^A_p, cn-\hbox{\rm AND})$ circuit computes the n-fan-in AND function, then its size is at least 2c'n.

Proof:    From the result of [3] and from Theorem 9 the statement is immediate. $\Box$ We should add, that Theorem 5 does not imply the CDH, but it greatly generalizes the lower bounds of [21] and of [3], and it works not only for the constant degree, but degree cn polynomials as well.

Corollary 6   There exist 0<c<1 and 0<c'<1, such that if the n fan-in AND function is computed by a circuit with a MODBq gate at the top, MODAp gates at the next level, where the inputs of each MODAp gate is an arbitrary integer-valued function of cn variables plus an arbitrary linear polynomial of n variables, then the circuit must contain at least 2c'n MODAp gates.

Proof:    First we convert the integer-valued function of cn variables into a polynomial over GF(p), for each MODAp gates. These polynomials have degree at most cn, and depend on at most cn variables. Consequently, the circuit is a (MODBq,MODAp,(cn-1)-AND) circuit, and Theorem 5 applies. $\Box$ We should mention, that Corollary 6 is much stronger than Yan and Parberry's result [21], since here the degree-sum of the inputs of each MODAp gate can be even exponentially large in n, vs. the small linear upper bound of [21].
next up previous
Next: The ID function Up: Applications of the Degree Previous: Applications of the Degree
Vince Grolmusz
1999-11-08