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.