Communications of the ACM

depth three circuit of size computing Detd over Q.

• Lower bounds for homogeneous depth three circuits already imply that the circuit obtained from such a depth reduction must necessarily be nonhomogeneous. Indeed, the resulting depth three circuits in our depth reduction are heavily nonhomogeneous in the sense that although the output polynomial is of degree d, intermediate gates compute formal polynomials of degree with the higher degree terms canceling out eventually!

The proof of Theorem 1 is rather quite short, and is obtained by using two known transformations (see Figure 3). But more than the proof, we believe that the train of thought that led to this theorem is more insightful. In this article, we shall present the result from the perspective of attempting to obtain a lower bound better than for depth four circuits.

2. TOWARD BETTER LOWER BOUNDS FOR DEPTH FOUR
We now begin to describe the depth reduction. The road map
we shall be following is given in Figure 3, and this section would
handle the first two arrows of Figure 3. From the depth reduc-
tion results of Agrawal and Vinay, 1 Koiran, 14 and Tavenas, 23 we
have the first arrow of Figure 3, that is, any polynomial-size
computation can be simulated by a depth four computation of
not-much-larger size. This implies that the problem of prov-
ing explicit super-polynomial-size lower bounds for arith-
metic circuits reduces to the following questionb:
The expression on the RHS is just a depth four circuit
with all multiplication fan-ins bounded by . We shall call
such circuits circuits.

We could first attempt solving the following “simpler”
question:
We shall call expressions like the above RHS as
circuits, where ∧ refers to the exponentiation.

It turns out that a solution to Problem 2 directly implies
a solution for Problem 1. The reason for this is that any
product can be rewritten as a sum of suitable powers, just
like xy = ((x+y) 2−x2−y2)/2. The following identity can be
obtained by a straightforward application of the inclusion–
exclusion principle.

As one might suspect from the similarity, the above equation is a special case of Ryser’s formula. We shall call this Fischer’s identity, 4 although he used a different identity to achieve the same transformation. Fischer’s identity can be thought of as converting a × gate to a Σ ∧ Σ circuit (Figure 4). Note that this identity is useful only as long as we can divide by r on both sides. Thus, if we are working only over integers, or over strange algebraic structures (such as fields of small characteristic) where r = 0, we cannot apply the above transformation. It is very important that this division by r! is allowed, and this is the also why this transformation cannot work if the resulting circuit must only involve integer constants.

Thus, if f is a formal polynomial admitting an expression of the form with deg , then f also admits an expression of the form where and . Hence, showing would immediately imply that . In other words, solving Problem 2 immediately yields a solution to Problem 1.

Just like we converted the top Π layer to exponentiations, we could also apply Fischer’s identity to the bottom multiplication gates also. Since each Qi is a formal polynomial of degree at most , the total number of monomials in any Qi is at most . Applying Fischer’s identity to those monomials as well yields an expression of the form where each lij is a linear polynomial and . We shall call such expressions analogously as circuits. The above discussion can therefore be summarized as follows.