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.
b Technically, the multiplications fan-ins ought to be at most 15 but we
shall take this liberty for the sake of better presentation.
Problem 1. Find an explicit n-variate degree d formal polynomial f such that any
expression of the form
with deg must have .
Problem 2. Find an explicit n-variate degree d formal polynomial f such that any
expression of the form
with deg must have .
×
...
r
+
2r
∧r ∧r
++
...
...
Figure 4. Transformation via Fischer’s identity.