Communications of the ACM

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: