DOI: 10.1145/3065468

Technical
Perspective
Low-Depth Arithmetic Circuits

By Avi Wigderson

To view the accompanying paper, visit doi.acm.org/10.1145/3065470

 

by Agrawal and Vinay, 1 which they called a “chasm at depth 4” appeared in 2008. Its clear message: proving lower bounds for (even homogeneous) depth- 4 circuits is as hard (or, for optimists, as useful) as proving lower bounds on general circuits. Extending the celebrated depth reduction technique of Valiant, Skyum, Berkowitz and Rackoff, 9 this paper (with subsequent improvements of Tavenas and Koiran) shows that any arithmetic circuit of size s computing a degree d polynomial can also be computed by a homogeneous depth- 4 circuit of size sΟ(√d ). For example, proving a subexponential nω(√n) lower bound for computing the permanent on n × n matrices, on such a weak constant-depth circuit would separate VP from VNP! But recall, even for depth- 3 we were stuck.

Next, a series of papers, mainly by subsets of the present authors and a few others got us extremely close to this goal! Using deep ideas and results from algebraic geometry originating from the work of Hilbert in commutative algebra, they have extended the method of partial derivatives to the much stronger “shifted partial derivatives” and combined with other ideas including very fine combinatorial analysis were able to reach the chasm, but not cross it. More precisely they proved lower bounds of nΩ(√n ) or both determinant and permanent. Note that for the determinant this lower bound is tight, and changing the Ω to ω in this expression for the permanent would thus separate the two and hence separate VP from VNP.

So far for depth 4. The following
paper proves that the very same
chasm actually exists in depth 3, at
least over fields of characteristic 0
like the rational numbers. More pre-
cisely, as above, every size s arithme-
tic circuit computing a polynomial of
degree d can be computed by a
depth- 3 circuit of size sΟ(√d )(which un-
A series of important works in the
1980s on constant-depth Boolean cir-
cuits gives a very good picture of their
limitations, including tight exponen-
tial lower bounds on extremely simple
functions like the symmetric func-
tions. The basic message is that con-
stant-depth (and polynomial size) is
an extremely weak class of algorithms.
Strangely (and specifically over large
enough fields) this intuition fails com-
pletely for arithmetic circuits. In 1980,
Ben-Or already made the important
simple observation that the symmet-
ric polynomials can be computed in
depth- 3 by a quadratic size formula!
So, the challenge to prove exponential
lower bounds for this simple model
was on. Such bounds were proved un-
der further restrictions (like homo-
geneity) by Nisan-Wigderson, 6 who
introduced important techniques of
partial derivatives and random restric-
tions to the study arithmetic circuits.
While the best general lower bound is
quadratic (matching Ben-Or’s result
for symmetric polynomials), there
was still a belief that constant depth
is a weak model and we should easily
prove much better bounds, for harder
functions like permanent and even
determinant. Still, no such progress
followed for over a decade.

A surprising and influential paper

While we generally
know more about
arithmetic circuits,
their power is
far from understood.

THE COMPUTATIONS OF polynomials (over a field, which we shall throughout assume is of zero or large enough characteristic) using arithmetic operations of addition and multiplication (and possibly division) are of course as natural as the computation of Boolean functions via logical gates, and capture many natural important tasks including Fourier transforms, linear algebra, matrix computations and more generally symbolic algebraic computations arising in many settings. Arithmetic circuits are the natural computational model for understanding the computational complexity of such tasks just like Boolean circuits are for Boolean functions. The presence of algebraic structure and mathematical tools supplied by centuries of work in algebra were a source of hope that understanding arithmetic circuits will be much faster and easier than their Boolean siblings. And while we generally know more about arithmetic circuits, their power is far from understood, and in particular, the arithmetic analog VP vs. VNP of the Boolean P vs. NP problem as formulated by Valiant8 is wide open.

The past few years have seen a revolution in our understanding of arithmetic circuits. Surprising new upper bounds, combined with new powerful techniques of proving lower bounds, have brought us to recognize the mysterious importance of very shallow circuits to capture the long-term goals of the field, and to pinpointing with uncommon precision the complexity of natural problems in this model. These developments have rejuvenated the hope, and give a concrete program, to the possible separation of Valiant’s classes VP and VNP. The following paper of Gupta et. al. on the “chasm at depth 3” is one of the culminations of this new understanding. I will now briefly explain the “chasm” phenomenon, and some of these developments, on which the authors of the paper elaborate.