How could one not be optimistic about this!
Some remarks. It is worth pointing out that all the lower
bounds recently obtained via the shifted partial derivatives
require an extremely delicate setting of parameters, with
very much involved calculations on binomial coefficients
(often working with the second-order terms in the Stirling’s approximation of n!). In fact, some of these proofs
have forced researchers to designa formal polynomials
(based on combinatorial objects called Nisan–Wigderson17
designs) with the sole purpose of making these calculations
1. 4. A new depth reduction
We present a surprising structural result about arithmetic circuits over Q that was obtained as a consequence of
attempting to break the barrier.
Theorem 1. Any n-variate degree d formal polynomial f that
can be computed by size s arithmetic circuits over Q can be
equivalently computed by a depth three circuit of size .
This effectively brings the chasm down to depth three. It is
worth noting that the blow-up from s to is the same asymptotics we get in the earlier reduction to depth four circuits. To give
a better sense of why such a result was surprising (at least to us),
we mention a few properties of the resulting depth three circuits.
• Although Detd has a polynomial-sized circuit, albeit of large
depth, the lower bound of Grigoriev and Karpinski’s6 show
that depth three circuits computing Detd that only uses integer constants in them must be of size 2Ω(d). This means that
the simulation in Theorem 1 must involve fractions in the
circuit. Thus, the proof of the theorem must be very algebraic in nature and depend very strongly on the underlying
field of constants. All prior depth reductions were field
independent, as they were very syntactic in nature. This
depth reduction must therefore be very different.
• As mentioned earlier, we knew of a 2Ω(d) lower bound for
depth three circuits over the integers for Detd. On the
algorithmic side, nothing significantly better than
writing Detd as a sum of d = dΘ(d) monomials was known.
It was strange that the best known ΣΠΣ circuit for
Permd was smaller than the best known ΣΠΣ circuit for
Detd over Q! Fortunately, our depth reduction yields a
showed that any ΣΠΣ arithmetic circuit over any fixed finite
field computing Detd must be of size at least 2Ω(d), thus also
implying that any ΣΠΣ arithmetic circuit over integers com-
puting Detd must be of size at least 2Ω(d).
Other restrictions of ΣΠΣ circuits have been studied
but till date, the best known lower bound in the general
ΣΠΣ case is the quadratic lower bound due to Shpilka and
21 Wigderson26 highlighted this frontier in arithmetic complexity by concluding his plenary talk on “P, NP,
and mathematics” at ICM 2006 with the problem of proving
super-polynomial-size lower bounds for ΣΠΣ circuits computing Detd. In fact, prior to our work, it was believed that
the any depth three circuit for Detd should be of size 2Ω(d).
Depth four circuits. For depth four circuits (also called
ΣΠΣΠ circuits), the depth-reduction results of Agrawal and Vi-
1 with subsequent strengthening by Koiran14 and Tavenas23
show that an n-variate degree d formal polynomial computed
by a size s arithmetic circuit can be equivalently simulated by a
depth four circuit of size . In fact, the resulting depth four
circuit has the property that all multiplication gates have fan-in
about . This implies that if we obtain an lower bound
for the size of such fan-in restricted depth four circuits com-
puting an explicit n-variate degree d formal polynomial, then we
obtain super-polynomial-size lower bounds for general circuits!
Thus, in essense, such depth four circuits are almost as hard as
general circuits. Agrawal and Vinay1 referred to this phenom-
enon as “the chasm at depth four.”
The first breakthrough was obtained8 by presenting
a lower bound of for Detd and Permd using a tech-
nique called “shifted partial derivatives.” This is a tech-
nique built over a known technique (introduced by Nisan
and Wigderson18) called the partial derivative method, and
enhanced with some intuition from algebraic-geometry.
Using shifted partial derivatives again, this bound was
subsequently improved5, 13, 15 to , and a flurry of results
gave more lower bounds for depth four circuits using very
similar techniques with matching upper bounds! In fact,
recent results12, 16 have obtained an for depth four
circuits even when there is no restriction on the fan-in, and
once again with matching upper bounds!
of size s
[ d] [ d]circuit
of size sO ( d )
[ d] [ d]
of size sO ( d )
of size s O ( d )
Saxena’s20 duality trick
and factorization over C
Σ∧ Σ∧ Σcircuits
Figure 3. Reduction to depth three.
To separate VP and VNP, one “merely” needs to study
depth four circuits and improve the known lower bounds
from to .
a Pun intended.