Saxena20 turns out to be exactly what we need for this
transformation. A similar transformation was also discovered earlier by Shpilka and Wigderson21 but statement below is from Ref.
Lemma 4 (Saxena’s20 Duality Trick). There exist univariate formal polynomials fij’s of degree at most b such that
It is worth noting that the degree of each term on the RHS
is sb, whereas the LHS just has degree b. This is the place
where nonhomogeneity is introduced. Applying Lemma 4
where f ĩj(y) = fij( ya). Since each fĩj(y) is a univariate polynomial, it can be factorized completely over the C, the
field of complex numbers. Hence, if fij( y) = ∏k(y − ζijk),
then we get
which is a depth three circuit! Thus, can be
expressed as a depth three circuit of size poly(s, a, b) over C.
Hence, any Σ∧Σ∧Σ circuit of size s can also be expressed
as a depth three circuit of size poly(s, a, b) over C. As mentioned earlier, the degree of intermediate computations in
the resulting depth three circuit is s ⋅ ab although the formal
polynomial computed is of degree just ab.
This already yields the depth reduction over complex
numbers. Lemma 2 states that any formal polynomial of
degree d over n variables that can be computed by an arithmetic circuit of size s can be computed by an Σ∧Σ∧Σ circuit
of size . By what we just noted, this can in-turn be
simulated by a depth three circuit over C of size poly .
The degree of intermediate computations in the resulting
depth three circuit is , which makes this a heavily nonhomogeneous circuit.
Although this depth reduction was done over the field
of complex numbers, a little more effort can yield a depth
three circuit over Q as well. This is a consequence of a
more general transformation to convert any circuit C of
size s computing a formal polynomial f ∈ Q [x1, …, xn] using
constants from an extension field of low degree into an
equivalent circuit C′ of not-much-larger size, thus yielding
Further, the transformation is also efficient in the sense
that the time required for this transformation is polynomial-time in the output size.
5. SOME CONSEQUENCES
An immediate consequence of such a depth reduction is new
constructions of depth three circuits for known efficiently computable formal polynomials. The permanent can be computed by a depth three circuit of size 2O(d) via Ryser’s formula.
Surprisingly, we knew of no such circuit for the determinant
polynomial. In fact, nothing significantly better than writing Detd
as a sum of d = dO(d) terms was known. With this depth reduction,
we now have a depth three circuit of size for Detd over Q.
Another immediate consequence is that strong enough
lower bounds (i.e., ) for ΣΠΣ circuits would yield super-polynomial-size lo wer bounds (i.e., nω( 1)) for general arithmetic
circuits. It is, however, unclear if nonhomogeneous depth three
circuit lower bounds are easier than homogenous depth four
circuit lower bounds. In the past, homogeneity has played a
crucial role in devising techniques for lower bounds.
The third consequence of such a depth reduction is implications to PIT. As mentioned earlier, PIT is the problem of checking if the formal polynomial computed by a given circuit C of size
s is zero or not. The goal is to do this deterministically in poly(s)
time, which is like an algebraic analog of showing P = co-RP.
A stronger form of PIT is the problem of Blackbox PIT where
we are only given oracle access to the circuit C. In the blackbox
model, we wish to construct a explicit hitting set of poly(s) size,
that is, a list of evaluations such that any nonzero circuit of size s
is guaranteed to evaluate to a nonzero value on one of the points.
A consequence of this depth reduction is that constructing
an explicit poly(s)-sized hitting set for depth three circuits of size
s implies an explicit hitting set of size sO(log s) for general arithmetic circuits of size s. This is exactly along the same lines as in the
depth reduction of Agrawal and Vinay1 for depth four circuits.
If the goal is to prove super-polynomial-size lower bounds for arith-
metic circuits, we can focus our attention on improving the current
lower bound (even slightly) for any of the following three models:
• ΣΠΣ circuits
A natural question here is—which of the above three models
should we attack?
Homogeneity has played a very important role in the past
lower bounds and proving lower bounds for such heavily nonhomogeneous depth three circuits appears daunting.
We believe the model to focus our attention on is the class
of circuits. We strongly believe that this is the
simplest form for which to prove super-polynomial arithmetic
circuit lower bounds. We state the problem again below to
emphasize our point.
The Problem. Find an explicit n-variate
degree d formal polynomial f such that any
expression of the form
with deg must have .