Communications of the ACM

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.