where each ca is in Q. The number of summands on the
RHS is bounded by the number of partitions of d, which
is at most by estimates of Hardy and Ramanujan.
9
Thus, the above equation is a ΣΠΣ∧ circuit of size
computing SYMd.
To convert this to a Σ∧Σ∧Σ circuit, we could use Fischer’s
identity again. At first sight, it appears as though this would
yield a blow up of 2d as some of the product gates could have
fan-in d. However, notice that the sum is over ai’s satisfying
∑ i ⋅ ai = d. Hence, there can be at most O ( ) of the ai’s
that are nonzero. By looking at Fischer’s identity applied
on more carefully, we see that it uses at most
distinct linear powers instead of
the naïve bound of 2d. This fact of expressing any degree d
monomial over m variables as a Σ∧Σ circuit of size dO(m) was
also observed by Ellison.
3
This results in an Σ∧Σ∧ circuit for SYMd(y1, ..., yD) of
size poly . Hence, any formal polynomial expressible as in ( 1) can be equivalently expressed as homogeneous
Σ∧Σ∧Σ circuit of size ⋅ poly (D, s, n). That is, if f admits
a poly-sized depth three circuit, then f also admits a homogeneous Σ∧Σ∧Σ circuit of size ⋅ poly (n). The following
lemma summarizes this discussion.
Lemma 3. Let f be an n-variate degree d formal polynomial,
that is, computable by depth three circuit of size s over Q. Then,
f is equivalently computable by a homogeneous Σ∧Σ∧Σ circuit
of size ⋅ poly (s).
Conversely, if f requires Σ∧Σ∧Σ circuits of size over Q
to compute it, then f requires depth three circuits of size .
4. PUTTING THEM TOGETHER
The two lemmas together weave an interesting picture
(Figure 5). On one hand, Lemma 2 states that a lower bound
of for Σ∧Σ∧Σ circuits would yield a super-polynomial-size lower bound for general arithmetic circuits. On the other,
Lemma 3 states that an lower bound for Σ∧Σ∧Σ circuits
would yield a lower bound of for depth three circuits.
Could this just be a coincidence? Or, is it the case that any
poly-sized arithmetic circuit can be equivalently expressed
as a depth three circuit of size over Q? As it turns out,
there is indeed a depth reduction to convert any arithmetic
circuit to a not-too-large depth three circuit over Q.
4. 1. The final piece
To complete the picture, it suffices to show how a ∧Σ∧ term
of the form can be expressed as a depth three
circuit. This would immediately imply a way to express
any Σ∧Σ∧Σ circuit as a ΣΠΣ. The following result of
Lemma 2. Let f be an n-variate degree d formal polynomial
that can be computed by size s arithmetic circuits over Q. Then,
f can be equivalently computed by a circuit
over Q of size .
Conversely, if f requires circuits of size ,
then f cannot be computed by polynomial-sized arithmetic circuits.
The only thing left to complete in our road map Figure 3 is
the last arrow. Before we describe the last step, we shall present some intuition about the mysterious intermediate model
of Σ∧Σ∧Σ circuits that we went to. However, readers who are
curious to know how the last step of the transformation works
may jump to Section 4. 1. For more intuition on Σ∧Σ∧Σ circuits, we shall keep this on hold and address another lower
bound question namely lower bound for depth three circuits.
3. TOWARD LOWER BOUNDS FOR DEPTH THREE
CIRCUITS
A depth three circuit computes a formal polynomial of the form
where each lij is a linear polynomial. If the circuit is homoge-
neous, then D ≤ deg f but we shall be interested in nonhomo-
geneous depth three circuits and hence D could potentially
be much larger than deg f. Using standard tricks, we may
assume that f is a homogeneous degree d formal polynomial
and we have an expression of the form
( 1)
where each αi ∈ F; and each lij is a homogeneous linear polynomial. By collecting degree d terms from the RHS, therefore follows that f can be written as
where SYMd(y1, .. ., yD) is the elementary symmetric polynomial of degree d defined as
These elementary symmetric polynomials can be expressed
in terms of the power symmetric polynomials, defined as
via the well-known Newton identities:
for Σ∧Σ∧Σ circuits
nω ( 1) LB
for general circuits for Σ∏Σ circuits
??
nω ( d) LB
nω ( d) LB
Figure 5. Power of ∑∧∑∧∑ circuits.