gates cannot even compute the parity of n-bits unless they
are of exponential size. This important result is now a part
of any course or textbook on complexity theory, such as Ref.
2
The analogous setting in arithmetic circuits to prove lower
bounds for constant depth (even depth of three or four) have
been challenging!
Valiant et al.
25 showed that if a formal polynomial f of
degree d can be computed by a circuit of size s then it can
in fact be computed by a circuit of depth O(log d ⋅ log s) and size
sO( 1). The contrapositive of this depth reduction is that if we can
prove super-polynomial-size lower bounds for O(log2 n) depth
circuits, then we can prove super-polynomial-size lower
bounds for general circuits.
Pushing this line of investigation of size-depth tradeoffs
further, recent work has considered reduction to circuits of
even smaller depth (with gates of unbounded fan-in) at the
cost of a super-polynomial increase in size. In this direction,
the work of Agrawal and Vinay1 and a subsequent strengthening by Koiran14 and Tavenas23 showed that if an n-variate
degree d polynomial f has circuits of size s = nO( 1) then f can
in fact be computed by depth four circuits of size . It is
worth noting that the trivial computation as a sum of monomials requires size , and a simple nonconstructive argument shows that most formal polynomials require
nΩ(d) size. In this light, the increase in size by only is
still very useful in the context of lower bounds.
This implies that one merely needs to prove a (good
enough) lower bound for depth four circuits in order to prove
lower bounds for arbitrary circuits. For example, if we could
show that Permd requires depth four circuits of size
then this would immediately imply that Permd requires general arithmetic circuits of size to compute it. Indeed,
motivated by this, recent lower bounds for depth four circuits have come very close to the threshold required to separate VP and VNP.
The following is a summary of the known depth reduction results:
1. 3. Lower bounds for shallow circuits
Depth three circuits. Progress in proving lower bounds
for arithmetic circuits has been admittedly slow. This is generally considered to be one of the most challenging problems in computer science. The difficulty of the problem has
led researchers to focus on natural subclasses of arithmetic
circuits. Bounded depth circuits being one such natural
subclass has received a lot of attention. The class of depth
three arithmetic circuits, also denoted as ΣΠΣ circuits, have
been intensely investigated as it is the shallowest nontrivial
subclass. Such a circuit C, as shown in Figure 2, computes a
formal polynomial of the form
where each lij(x) is a linear polynomial over the input variables. ΣΠΣ circuits arise naturally in the investigation of the
complexity of polynomial multiplication and matrix multiplication. Moreover, the optimal formula/circuit for some
well-known families of formal polynomials are in fact depth
three circuits. In particular, the best known circuit for computing Permd is known as Ryser’s formula19:
which is a depth three circuit of size O(d2 ⋅ 2d). Ryser’s formula is another example of a nontrivial speedup of algebraic
computation.
Quite a few lower bounds have been obtained for restrictions of depth three circuits. Nisan and Wigderson18 studied
depth three circuits under the restriction of homogeneity.
A homogeneous circuit is one where the degree of all intermediate computations are bounded by the degree of the
output polynomial. Nisan and Wigderson18 showed that over
any field F, any homogeneous ΣΠΣ circuit computing the
determinant Detd must be of size 2Ω(d). They also gave a concrete example to show that nonhomogeneous depth three
circuits can be exponentially more powerful than homogeneous depth three circuits. For general circuits, however,
homogeneity may be assumed without loss of generality. But
the same cannot be said about very shallow circuits.
Notations. We recall that, f (n) = Ω( g (n)) means that
for some constant c, f(n) is greater than c ⋅ g (n) for
sufficiently large n. Furthermore, f (n) = ω ( g (n) ) means
that for every constant c, f (n) is larger than c ⋅ g (n) for
sufficiently large n.
An n-variate degree d poly
computable by a size s circuit
⇓
25
computable by a size sO( 1) circuit
of O(log d) depth
⇓
1, 14, 23
computable by a size circuit
of depth four
x1 x2 x3
1
++++++
×××
+
Figure 2.. A depth three circuit.