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 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 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:

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 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. 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. 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: The ID function Up: Applications of the Degree Previous: Applications of the Degree
Vince Grolmusz
1999-11-08