Communications of the ACM

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 amenable.

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 Wigderson. 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-
nay, 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!