Authors Mrinal Kumar, Shubhangi Saraf,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33
www.theoryofcomputing.org
S PECIAL ISSUE : CCC 2016
Arithmetic Circuits with
Locally Low Algebraic Rank
Mrinal Kumar∗ Shubhangi Saraf†
Received April 30, 2016; Revised June 7, 2017; Published September 1, 2017
Abstract: In recent years, there has been a flurry of activity towards proving lower bounds
for homogeneous depth-4 arithmetic circuits (Gupta et al., Fournier et al., Kayal et al., Kumar-
Saraf), which has brought us very close to statements that are known to imply VP 6= VNP. It
is open if these techniques can go beyond homogeneity, and in this paper we make progress
in this direction by considering depth-4 circuits of low algebraic rank, which are a natural
extension of homogeneous depth-4 arithmetic circuits.
A depth-4 circuit is a representation of an N-variate, degree-n polynomial P as
T
P = ∑ Qi1 · Qi2 · · · · Qit ,
i=1
where the Qi j are given by their monomial expansion. Homogeneity adds the constraint
that for every i ∈ [T ], ∑ j deg(Qi j ) = n. We study an extension, where, for every i ∈ [T ],
A conference version of this paper appeared in the Proceedings of the Conference on Computational Complexity, 2016 [27].
∗ Research supported in part by NSF grant CCF-1253886 and by a Simons Graduate Fellowship.
† Research supported by NSF grant CCF-1350572.
ACM Classification: F.1.3
AMS Classification: 68Q15, 68Q17
Key words and phrases: algebraic rank, arithmetic circuits, hitting sets, lower bounds, non-
homogeneous depth-4 circuits, partial derivatives, polynomial identity testing, projected shifted partials
© 2017 Mrinal Kumar and Shubhangi Saraf
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2017.v013a006
M RINAL K UMAR AND S HUBHANGI S ARAF
the algebraic rank of the set {Qi1 , Qi2 , . . . , Qit } of polynomials is at most some parameter
k. We call this the class of ΣΠ(k) ΣΠ circuits. Already for k = n, these circuits are a strong
generalization of the class of homogeneous depth-4 circuits, where in particular t ≤ n (and
hence k ≤ n).
We study lower bounds and polynomial identity tests for such circuits and prove the
following results.
1. Lower bounds. We give an explicit family of polynomials {Pn } of degree n in N =
nO(1) variables in VNP, such that any ΣΠ(n) ΣΠ circuit computing Pn has size at least
√
exp (Ω( n log N)). This strengthens and unifies two lines of work: it generalizes the
recent exponential lower bounds for homogeneous depth-4 circuits (Kayal et al. and
Kumar-Saraf) as well as the Jacobian based lower bounds of Agrawal et al. which
worked for ΣΠ(k) ΣΠ circuits in the restricted setting where T · k ≤ n.
2. Hitting sets. Let ΣΠ(k) ΣΠ[d] be the class of ΣΠ(k) ΣΠ circuits with bottom fan-in at
most d. We show that if d and k are at most Poly(log N), then there is an explicit hitting
set for ΣΠ(k) ΣΠ[d] circuits of size quasipolynomially bounded in N and the size of the
circuit. This strengthens a result of Forbes who constructed such quasipolynomial-size
hitting sets in the setting where d and t are at most Poly(log N).
A key technical ingredient of the proofs is a result which states that over any field of
characteristic zero (or sufficiently large characteristic), up to a translation, every polynomial
in a set of polynomials can be written as a function of the polynomials in a transcendence
basis of the set. We believe this may be of independent interest. We combine this with
methods based on shifted partial derivatives to obtain our final results.
1 Introduction
Arithmetic circuits are natural algebraic analogues of Boolean circuits, with the logical operations being
replaced by sum and product operations over the underlying field. Valiant [44] developed the complexity
theory for algebraic computation via arithmetic circuits and defined the complexity classes VP and VNP
as the algebraic analogs of complexity classes P and NP respectively. We refer the interested reader to
the survey by Shpilka and Yehudayoff [42] for more on arithmetic circuits.
Two of the most fundamental questions in the study of algebraic computation are the questions of
polynomial identity testing(PIT)1 and the question of proving lower bounds for explicit polynomials. It
was shown by structural results known as depth reductions [2, 24, 43] that strong enough lower bounds or
PIT results for just (homogeneous) depth-4 circuits, would lead to superpolynomial lower bounds and
derandomized PIT for general circuits too. Consequently, depth-4 arithmetic circuits have been the focus
of much investigation in the last few years.
Just in the last few years, we have seen rapid progress in proving lower bounds for homogeneous
depth-4 arithmetic circuits, starting with the work of Gupta et al. [13] who proved exponential lower
1 Given an arithmetic circuit, the problem is to decide if it computes the identically zero polynomial. In the whitebox setting
we are allowed to look inside the wirings of the circuit, while in the blackbox setting, we can only query the circuit at some
points.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 2
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
bounds for homogeneous depth-4 circuits with bounded bottom fan-in and terminating with the results of
Kayal et al. [18] and of the authors of this paper [29], which showed exponential lower bounds for general
homogeneous depth-4 circuits. Any asymptotic improvement in the exponent of these lower bounds
would lead to superpolynomial lower bounds for general arithmetic circuits.2 Most of this progress was
based on an understanding of the complexity measure of the family of shifted partial derivatives of a
polynomial (this measure was introduced by Kayal [17]), and other closely related measures.
Although we now know how to use these measure to prove such strong lower bounds for homogeneous
depth 4 circuits, the best known lower bounds for non-homogeneous depth three circuits over fields
of characteristic zero are just cubic [41, 39, 21], and those for non-homogeneous depth-4 circuits over
any field except F2 are just about superlinear [33]. It remains an extremely interesting question to get
improved lower bounds for these circuit classes.
In sharp contrast to this state of knowledge on lower bounds, the problem of polynomial identity
testing is very poorly understood even for depth three circuits. Till a few years ago, almost all the PIT
algorithms known were for extremely restricted classes of circuits and were based on diverse proof
techniques (for instance, [7, 23, 15, 22, 14, 37, 38, 36, 1, 10, 30]). The paper by Agrawal et al. [1] gave a
unified proof of several of them.
It is a big question to go beyond homogeneity (especially for proving lower bounds) and in this paper
we make progress towards this question by considering depth-4 circuits of low algebraic rank,3 which are
a natural extension of homogeneous depth-4 arithmetic circuits.
A depth-4 circuit is a representation of an N-variate, degree-n polynomial P as
T
P = ∑ Qi1 · Qi2 · · · · Qit
i=1
where the Qi j are given by their monomial expansion. Homogeneity adds the constraint that for every
i ∈ [T ], ∑ j deg(Qi j ) = n. We study an extension where, for every i ∈ [T ], the algebraic rank of the set
{Qi1 , Qi2 , . . . , Qit } of polynomials is at most some parameter k. We call this the class of ΣΠ(k) ΣΠ circuits.
Already for k = n, these circuits are a strong generalization of the class of homogeneous depth-4 circuits,
where in particular t ≤ n (and hence k ≤ n).
We prove exponential lower bounds for ΣΠ(k) ΣΠ circuits for k ≤ n and give quasipolynomial time
deterministic polynomial identity tests for ΣΠ(k) ΣΠ circuits when k and the bottom fan-in are bounded
by Poly(log N). All our results actually hold for a more general class of circuits, where the product gates
at the second level can be replaced by an arbitrary circuits whose inputs are polynomials of algebraic
rank at most k. In particular, our results hold for representations of a polynomial P as
T
P = ∑ Ci (Qi1 , Qi2 , . . . , Qit )
i=1
where, for every i ∈ [T ], Ci is an arbitrary polynomial function of t inputs, and the algebraic rank of the
set {Qi1 , Qi2 , . . . , Qit } of polynomials is at most some parameter k.
2 We refer the interested reader to the surveys of recent lower bounds results by Saptharishi [35, 34].
3 The algebraic rank of a set of polynomials is the size of the maximal subset of this set which are algebraically independent.
See Section 2 for formal definitions.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 3
M RINAL K UMAR AND S HUBHANGI S ARAF
1.1 Some background and motivation
Before we more formally define the model and state our results, we give some background and motivation
for studying this class of circuits.
Strengthening of the model of homogeneous depth-4 circuits. As already mentioned, we know very
strong exponential lower bounds for homogeneous depth-4 arithmetic circuits. In contrast, for general
(non-homogeneous) depth-4 circuits, we know only barely superlinear lower bounds, and it is a challenge
to obtain improved bounds. ΣΠ(k) ΣΠ circuits with k as large as n (the degree of the polynomial being
computed), which is the class we study in this paper, is already a significant strengthening of the model of
homogeneous depth-4 circuits (since the intermediate degrees could be exponentially large). We provide
exponential lower bounds for this model. Note that when k = N, ΣΠ(k) ΣΠ circuits would capture general
depth-4 arithmetic circuits.
Low algebraic rank and lower bounds. In a recent paper, Agrawal et al. [1] studied the notion of
circuits of low algebraic rank and by using the Jacobian to capture the notion of algebraic independence,
they were able to prove exponential lower bounds for a certain class of arithmetic circuits.4 They showed
that over fields of characteristic zero, for any set {Q1 , Q2 , . . . , Qt } of polynomials of sparsity at most s and
algebraic rank k, any arithmetic circuit of the form C(Q1 , Q2 , . . . , Qt ) which computes the determinant
polynomial for an n × n symbolic matrix must have s ≥ exp (n/k). Note that if k = Ω(n), then the lower
bound becomes trivial. The lower bounds in this paper strengthen these results in two ways.
1. Our lower bounds hold for a (potentially) richer class of circuits. In the model considered by [1],
one imposes a global upper bound k on the rank of all the Qi feeding into some polynomial C. In
our model, we can take exponentially many different sets of polynomials Qi , each with bounded
rank, and apply some polynomial function to each of them and then take a sum.
2. Our lower bounds are stronger—we obtain exponential lower bounds even when k is as large as the
degree of the polynomial being computed.
Algebraic rank and going beyond homogeneity. Even though we know exponential lower bounds
for homogeneous5 depth-4 circuits, the best known lower bounds for non-homogeneous depth-4 circuits
are barely superlinear [33].
Grigoriev-Karpinski [11], Grigoriev-Razborov [12] and Shpilka-Wigderson [41] outlined a program
based on “rank” to prove lower bounds for arithmetic circuits. They used the notion of “linear rank” and
used it to prove lower bounds for depth-3 arithmetic circuits in the following way. Let C = ∑Ti=1 ∏tj=1 Li j
be a depth three (possibly nonhomogeneous) circuit computing a polynomial P of degree-n. Now, partition
the inputs to the top sum gate to two halves, C1 and C2 based on the rank of the inputs feeding into it in
the following way. For each i ∈ [T ], if the linear rank of the set {Li j : j ∈ [t]} of polynomials is at most k
(for some threshold k), then include the gate i into the sum C1 , else include it into C2 . Therefore,
C = C1 +C2 .
4 Even more significantly they also give efficient PIT algorithms for the same class of circuits.
5 These results, in fact, hold for depth-4 circuits with not-too-large formal degree.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 4
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
Their program had two steps.
1. Show that the subcircuit C1 is weak with respect to some complexity measure, and thus prove a
lower bound for C1 (and hence C) when C2 is trivial.
2. Also since C2 is “high rank,” show that there are many inputs for which C2 is identically zero. Then
try to look at restrictions over which C2 is identically zero, and show that the lower bounds for C1
continue to hold.
The following is the natural generalization of this approach to proving lower bounds for depth-4
circuits. Let C = ∑Ti=1 ∏tj=1 Qi j be a depth-4 circuit computing a polynomial P of degree-n. Note that in
general, the formal degree of C could be much larger than n. Now, we partition the inputs to the top sum
gate to two halves, C1 and C2 based on the algebraic rank of the inputs feeding into it in the following
way. For each i ∈ [T ], if the algebraic rank of the set {Qi j : j ∈ [t]} of polynomials is at most k (for some
threshold k), then we include the gate i into the sum C1 else we include it into C2 . Therefore,
C = C1 +C2 .
To implement the G-K, G-R and S-W program, as a first step one would show that the subcircuit C1 is
weak with respect to some complexity measure, and thus prove a lower bound for C1 (and hence C) when
C2 is trivial. The second step would be to try to look at restrictions over which C2 is identically zero, and
show that the lower bounds for C1 continue to hold.
For the case of depth-4 circuits, even the first step of proving lower bounds when C2 is trivial was not
known prior to this work (even for k = 2). Our results in this paper are an implementation of this first
step, as we prove exponential lower bounds when the algebraic rank of inputs into each of the product
gates is at most n (the degree of the polynomial being computed).
Connections to divisibility testing. Recently, Forbes [9] showed that given two sparse multivariate
polynomials P and Q, the question of deciding if P divides Q can be reduced to the question of polynomial
identity testing for ΣΠ(2) ΣΠ circuits. This question was one of the original motivations for this paper.
Although we are unable to answer this question in general, we make some progress towards it by giving a
quasipolynomial identity tests for ΣΠ(k) ΣΠ circuits when the various Qi j feeding into the circuit have
degree bounded by Poly(log N) (and we are also able to handle k as large as Poly(log N)).
Low algebraic rank and PIT. Two very interesting PIT results which are also very relevant to the
results in this paper are those of Beecken et al. [3] and those of Agrawal et al. [1]. The key idea explored
in both these papers is that of algebraic independence. Together, they imply efficient deterministic PIT for
polynomials which can be expressed in the form C(Q1 , Q2 , . . . , Qt ), where C is a circuit of polynomial
degree and Q0i s are either sparse polynomials or product of linear forms, such that the algebraic rank of
{Q1 , Q2 , . . . , Qt } is bounded.6 This approach was extremely powerful as Agrawal et al. [1] demonstrate
that they can use this approach to recover many of the known PIT results, which otherwise had very
different proofs techniques. The PIT results of this paper hold for a variation of the model just described
and we describe it in more detail in Section 1.3.3.
6 See Section 2 for definitions.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 5
M RINAL K UMAR AND S HUBHANGI S ARAF
Polynomials with low algebraic rank. In addition to potential applications to arithmetic circuit com-
plexity, it seems an interesting mathematical question to understand the structure of a set of algebraically
dependent polynomials. In general, our understanding of algebraic dependence is not as clear as our
understanding of linear dependence. For instance, we know that if a set of polynomials is linearly
dependent, then every polynomial in the set can be written as a linear combination of the polynomials in
the basis. However, for higher degree dependencies (linear dependence is dependency of degree-1), we
do not know any such clean statement. As a significant core of our proofs, we prove a statement of this
flavor in Lemma 1.10.
We now formally define the model of computation studied in this paper, and then state and discuss
our results.
1.2 Model of computation
We start with the definition of algebraic dependence. See Section 2 for more details.
Definition 1.1 (Algebraic independence and algebraic rank). Let F be any field. A set
Q = {Q1 , Q2 , . . . , Qt } ⊆ F[X1 , X2 , . . . , XN ]
of polynomials is said to be algebraically independent over F if there is no nonzero polynomial R ∈
F[Y1 ,Y2 , . . . ,Yt ] such that R(Q1 , Q2 , . . . , Qt ) is identically zero.
A maximal subset of Q which is algebraically independent is said to be a transcendence basis of Q
and the size of such a set is said to be the algebraic rank of Q.
It is known that algebraic independence satisfies the Matroid property [31], and therefore the algebraic
rank is well defined. We are now ready to define the model of computation.
Definition 1.2. Let F be any field. A ΣΠ(k) ΣΠ circuit C in N variables over F is a representation of an
N-variate polynomial as
T
C = ∑ Qi1 · Qi2 · · · Qit
i=1
for some t, T such that for each i ∈ [T ], the algebraic rank of the set {Qi j : j ∈ [t]} of polynomials is at
most k. Additionally, if for every i ∈ [T ] and j ∈ [t], the degree of Qi j is at most d, we say that C is a
ΣΠ(k) ΣΠ[d] circuit.
We will state all our results for ΣΠ(k) ΣΠ and ΣΠ(k) ΣΠ[d] circuits. However, the results in this paper
hold for a more general class of circuits where the product gates at the second level can be replaced by
arbitrary polynomials. This larger class of circuits will be crucially used in our proofs and we define it
formally below.
Definition 1.3. Let F be any field. A ΣΓ(k) ΣΠ circuit C in N variables over F is a representation of an
N-variate polynomial as
T
C = ∑ Γi (Qi1 , Qi2 , . . . , Qit )
i=1
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 6
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
for some t, T such that Γi is an arbitrary polynomial in t variables, and for each i ∈ [T ], the algebraic
rank of the set {Qi j : j ∈ [t]} of polynomials is at most k. Additionally, if for every i ∈ [T ] and j ∈ [t], the
degree of Qi j is at most d, we say that C is a ΣΓ(k) ΣΠ[d] circuit.
Definition 1.4 (Size of a circuit). The size of a ΣΠ(k) ΣΠ or a ΣΓ(k) ΣΠ circuit C is defined as the maximum
of T and the number of monomials in the set
[
Support(Qi j ) .
i∈[T ], j∈[t]
Here for a polynomial Q, Support(Q) is the set of all monomials which appear with a non-zero coefficient
in Q.
A ΣΠ(k) ΣΠ circuit C for which the polynomials {Qi j : i ∈ [T ], j ∈ [t]} are homogeneous polynomials
such that for every i ∈ [T ],
∑ deg(Qi j ) = deg(P)
j∈[t]
(where P is the polynomial being computed)7 is the class of homogeneous depth-4 circuits. If we drop
the condition of homogeneity, then in general the value of t could be much larger than deg(P) and the
degrees of the Qi j could be much larger than deg(P). Thus, the class of ΣΠ(k) ΣΠ circuits with k equaling
the degree of the polynomial being computed could potentially be a larger class of circuits compared to
that of homogeneous depth-4 circuits.
Also note that in the definition of ΣΠ(k) ΣΠ circuits, the bound on the algebraic rank is local for each
i ∈ [T ], and in general, the algebraic rank of the entire set {Qi j : i ∈ [T ], j ∈ [t]} can be as large as N.
1.3 Our results
We now state our results and discuss how they relate to other known results.
1.3.1 Lower bounds
As our first result, we give exponential lower bounds on the size of ΣΠ(k) ΣΠ circuits computing an explicit
polynomial when the algebraic rank (k) is at most the degree (n) of the polynomial being computed.
Theorem 1.5. Let F be any field of characteristic zero.8 There exists a family {Pn } of polynomials in
VNP, such that Pn is a polynomial of degree-n in N = nO(1) variables with 0, 1 coefficients, and for any
ΣΠ(k) ΣΠ circuit C, if k ≤ n and if C computes Pn over F, then
√
Size(C) ≥ N Ω( n) .
7 Observe that in this case, k ≤ t ≤ deg(P).
8 Sufficiently large characteristic suffices.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 7
M RINAL K UMAR AND S HUBHANGI S ARAF
Remark 1.6. From our proofs it follows that our lower bounds hold for the more general class of ΣΓ(k) ΣΠ
circuits, but for the sake of simplicity, we state our results in terms of ΣΠ(k) ΣΠ circuits. We believe it is
likely that the lower bounds also hold for a polynomial in VP and it would be interesting to know if this
is indeed true.9
Remark 1.7. Even though we state Theorem 1.5 for k ≤ n, the proof goes through as long as k is any
polynomial in n and N is chosen to be an appropriately large polynomial in n.
1.3.2 Comparison to known results
As we alluded to in the introduction, ΣΠ(k) ΣΠ circuits for k ≥ n subsume the class of homogeneous depth-
4 circuits. Therefore, Theorem 1.5 subsumes the lower bounds for homogeneous depth-4 circuits [18, 29]
for sufficiently large characteristic. Moreover, it also subsumes and generalizes the lower bounds of
Agrawal et al. [1] since their lower bounds hold only if the algebraic rank of the entire set {Qi j : i ∈
[T ], j ∈ [t]} of polynomials is bounded, while for Theorem 1.5, we only need upper bounds on the
algebraic rank separately for every i ∈ [T ].
1.3.3 Polynomial identity tests
We show that there is a quasipolynomial size hitting set for all polynomials P ∈ ΣΠ(k) ΣΠ[d] for bounded
d and k. More formally, we prove the following theorem.
Theorem 1.8. Let F be any field of characteristic zero.10 Then, for every N, there exists a set H ⊆ FN
such that
|H| ≤ exp(O(logO(1) N))
and for every nonzero N-variate polynomial P over F which is computable by a ΣΠ(k) ΣΠ[d] circuit with
d, k ≤ log N and size Poly(N), there exists an h ∈ H such that P(h) 6= 0. Moreover, the set H can be
explicitly constructed in time
exp(O(logO(1) N)) .
We now mention some remarks about Theorem 1.8.
Remark 1.9. It follows from our proof that the hitting set works for the more general class of ΣΓ(k) ΣΠ[d]
circuits with d, k ≤ log N, size Poly(N) and formal degree at most Poly(N).
1.3.4 Comparison to known results
The two known results closest to our PIT result are the results of Forbes [9] and the results of Agrawal et
al. [1]. Forbes [9] studies PIT for the case where the number of distinct inputs to the second level product
gates in a depth-4 circuit with bounded bottom fan-in also bounded (which naturally also bounds the
algebraic rank of the inputs), and constructs quasipolynomial-size hitting sets for this case. On the other
hand, we handle the case where there is no restriction on the number of distinct inputs feeding into the
9 More on this in Section 6.
10 Sufficiently large characteristic suffices.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 8
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
second level product gates, but we need to bound the bottom fan-in as well as the algebraic rank. In this
sense, the results in this paper are a generalization of the results of Forbes [9].
Agrawal et al. [1] give a construction of polynomial-size hitting sets in the case when the total
algebraic rank of the set {Qi j : i ∈ [T ], j ∈ [t]} is bounded, but they can work with unbounded d. On
the other hand, the size of our hitting set depends exponentially on d, but requires only local algebraic
dependencies for every i ∈ [T ]. So, these two results are not comparable, although there are similarities in
the sense that both of them aim to use the algebraic dependencies in the circuit. In general, summation is
a tricky operation with respect to designing PIT algorithms (as opposed to multiplication), so it is not
clear if the ideas in the work of Agrawal et al. [1] can be somehow adapted to prove Theorem 1.8.
1.3.5 From algebraic dependence to functional dependence
Our lower bounds and PIT results crucially use the following lemma, which (informally) shows that over
fields of characteristic zero, up to a translation, every polynomial in a set of polynomials can be written
as a function of the polynomials in transcendence basis.11 We now state the lemma precisely.
Lemma 1.10 (Algebraic dependence to functional dependence). Let F be any field of characteristic zero
or sufficiently large positive characteristic. Let Q = {Q1 , Q2 , . . . , Qt } be a set of polynomials in N vari-
ables such that the algebraic rank of Q equals k. Let di = deg(Qi ) (i ∈ [t]) and let B = {Q1 , Q2 , . . . , Qk }
be a maximal algebraically independent subset of Q. Then, there exists an a = (a1 , a2 , . . . , aN ) in FN and
polynomials Fk+1 , Fk+2 , . . . , Ft in k variables such that ∀i ∈ {k + 1, k + 2, . . . ,t}
Qi (X + a) = Hom≤di Fi (Q1 (X + a), Q2 (X + a), . . . , Qk (X + a)) .
Here, for any polynomial P, we use Hom≤i [P] to refer to the sum of homogeneous components of P of
degree at most i.12
Even though the lemma seems a very basic statement about the structure of algebraically dependent
polynomials, to the best of our knowledge this was not known before. The proof builds upon a result on
the structure of roots of multivariate polynomials by Dvir et al. [8]. Observe that for linear dependence,
the statement analogous to that of Lemma 1.10 is trivially true. We believe that this lemma might be of
independent interest (in addition to its applications in this paper).
In fact, the lemma holds for a random choice of the vector a chosen uniformly from a large enough
grid in FN .
Remark 1.11. In a recent result, Pandey et al. [32] show that this connection between algebraic depen-
dence and functional dependence continues to hold over fields of small characteristic. Consequently, they
show that the results of this paper also hold over fields of small characteristic.
11 A transcendence basis of a set of polynomials is a maximal subset of the polynomials with the property that its elements are
algebraically independent. For more on this see Section 2.
12 For a more precise definition see Definition 2.2.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 9
M RINAL K UMAR AND S HUBHANGI S ARAF
1.4 Proof overview
Even though the results in this paper seem related to the results in [1] (both exploiting some notion of low
algebraic rank), the proof strategy and the way algebraic rank is used are quite different. We now briefly
outline our proof strategy.
We first discuss the overview of proof for our lower bound.
Let Pn be the degree-n polynomial we want to compute, and let C be a ΣΠ(k) ΣΠ circuit computing it,
with k = n. Then C can be represented as
T t
C = ∑ ∏ Qi j .
i=1 j=1
From definitions, we know that for every i ∈ [T ], the algebraic rank of the set {Qi1 , Qi2 , . . . , Qit } of
polynomials is at most k(= n). We want to give a lower bound on the size of C.
Instead of proving our result directly for ΣΠ(k) ΣΠ circuits, it will be very useful for us to go to the
significantly strengthened class of ΣΓ(k) ΣΠ circuits and prove our result for that class. Thus we think of
our circuit C as being expressed as
T
C = ∑ Ci (Qi1 , Qi2 , . . . , Qit )
i=1
where the Ci can be arbitrary polynomial functions of the inputs feeding into them. Note that we define
the size of a ΣΓ(k) ΣΠ circuit to be the maximum of the top fan-in T , and the maximum of the number
of monomials in any of the polynomials Qi j feeding into the circuit. Thus we completely disregard the
complexities of the various polynomial function gates at the second level. If we are able to prove a lower
bound for this notion of size, then if the original circuit is actually a ΣΠ(k) ΣΠ circuit then it will also be
as good a lower bound for the usual notion of size.
Our lower bound has two key steps. In the first step we prove the result in the special case where
t ≤ n2 . In the second step we show how to “almost” reduce to the case of t ≤ n2 .
Step (1) : t ≤ n2 . In the representation of C as a ΣΓ(k) ΣΠ circuit, the value of t is at most n2 . Lower
bounds for this case turn out to be similar to lower bounds for homogeneous depth-4 circuits. In this case
we borrow ideas from prior works [13, 18, 29] and show that the dimension of projected shifted partial
derivatives of C is not too large. Most importantly, we can use the chain rule for partial derivatives to
obtain good bounds for this complexity measure, independent of the complexity of the various Ci .
Recall however that in our final result, t can be actually much larger than n2 . Indeed the circuit C
can be very far from being homogeneous, and for general depth-4 circuits, we do not know good upper
bounds on the complexity of shifted partial derivatives or projected shifted partial derivatives. Also, in
general, it is not clear if these measures are really small for general depth-4 circuits.13 It is here that
the low algebraic rank of {Qi1 , Qi2 , . . . , Qit } proves to be useful, and that brings us to the crux of our
argument.
13 Indeed, as an earlier result of the authors [26] shows, even homogeneous depth-4 circuits can have very large shifted partial
derivative complexity.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 10
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
Step (2) : Reducing to the case where t ≤ n2 . A key component of our proof, which is formalized in
Lemma 3.5 shows that over any field of characteristic zero (or sufficiently large characteristic), up to a
translation, every polynomial in a set of polynomials can be written as a function of the homogeneous
components of the polynomials in the transcendence basis.
More formally, there exists an a ∈ FN such that C(X + a) can be expressed as
T
C(X + a) = ∑ Ci0 (Hom[Qi1 (X + a)], Hom[Qi2 (X + a)], . . . , Hom[Qik (X + a)])
i=1
where for a degree-d polynomial F, Hom[F] denotes the d + 1-tuple of homogeneous components of F.
Moreover, Qi1 , Qi2 , . . . , Qik are the polynomials in the transcendence basis.
The crucial gain in the above transformation is that the arity of each of the polynomials Ci0 is (d +1)×k
and not t (where d is an upper bound on the degrees of the Qi j ). Now by assumption k ≤ n, and moreover
without loss of generality we can assume d ≤ n since homogeneous components of Qi j of degree larger
than n can be dropped since they do not contribute to the computation of a degree-n polynomial. Thus we
have essentially reduced to the case where t ≤ n2 .
One loss by this transformation is that the polynomials {Ci0 } might be much more complex and with
much higher degrees than the original polynomials {Ci }. However this will not affect the computation of
our complexity measure. Another loss is that we have to deal with the translated polynomial C(X + a).
This introduces some subtleties into our computation as it could be that Qi j (X) is a sparse polynomial but
Qi j (X + a) is far from being sparse. Neither of these issues is very difficult to deal with, and we are able
to get strong bounds for the measure, based on projected shifted partial derivatives, for such circuits. The
proof of Lemma 3.5 essentially follows from Lemma 1.10.
The proof of Lemma 1.10 crucially uses a result of Dvir, Shpilka and Yehudayoff [8] which shows
that up to some minor technical conditions (which are not very hard to satisfy), factors of a polynomial
f ∈ F[X1 , X2 , . . . , XN ,Y ] of the form Y − p(X1 , X2 , . . . , XN ) where p ∈ F[X1 , X2 , . . . , XN ] can be expressed
as polynomials in the coefficients when viewing f as an element of F[X1 , X2 , . . . , XN ][Y ]. This is relevant
since if a set of t polynomials is algebraically dependent, then there is a non-zero t-variate polynomial
which vanishes when composed with this tuple. We use this vanishing to prove the lemma.
The PIT results follows a similar initial setup and use of Lemma 1.10. We then use a result of
Forbes [9] to show that the polynomial computed by C has a monomial of small support, which is then
detected using the standard idea of using Shpilka-Volkovich generators [40].
1.5 Organization of the paper
The rest of the paper is organized as follows. In Section 2, we state some preliminary definitions and
results that are used elsewhere in the paper. In Section 3, we describe our use of low algebraic rank and
prove Lemma 3.5. We prove Theorem 1.5 in Section 4 and Theorem 1.8 in Section 5. We end with some
open questions in Section 6.
2 Preliminaries
In this section we introduce some notation and definitions for the rest of the paper.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 11
M RINAL K UMAR AND S HUBHANGI S ARAF
2.1 Notation
1. For an integer i, we denote the set {1, 2, . . . , i} by [i].
2. By X, we mean the set {X1 , X2 , . . . , XN } of variables.
3. For a field F, we use F[X] to denote the ring of all polynomials in X1 , X2 , . . . , XN over the field F.
For brevity, we denote a polynomial P(X1 , X2 , . . . , XN ) ∈ F[X] by P(X).
4. The support of a monomial α is the set of variables which appear with a non-zero exponent in α.
5. We say that a function f (N) is quasipolynomially bounded in N if there exists a positive abso-
lute constant c, such that for all N sufficiently large, f (N) < exp(logc N). For brevity, if f is
quasipolynomially bounded in N, we say that f is quasipolynomial in N.
6. In this paper, unless otherwise stated, F is a field of characteristic zero.
7. Given a polynomial P and a valid monomial ordering Π, the leading monomial of P is the monomial
with a nonzero coefficient in P which is maximal according to Π. Similarly, the trailing monomial
in P is the monomial which is minimal among all monomials in P according to Π.
8. All our logarithms are to the base e.
2.2 Algebraic independence
We formally defined the notion of algebraic independence and algebraic rank in Definition 1.1. For more
on algebraic independence and related discussions, we refer the reader to the excellent survey by Chen,
Kayal and Wigderson [4] and earlier papers [3, 1].
For a tuple Q = (Q1 , Q2 , . . . , Qt ) of algebraically dependent polynomials, we know that there is
a nonzero t-variate polynomial R (called a Q-annihilating polynomial) such that R(Q1 , Q2 , . . . , Qt ) is
identically zero. A natural question is to ask, what kind of bounds on the degree of R can we show, in
terms of the degrees of Qi . The following lemma of Kayal [16] gives an upper bound on the degree of
annihilating polynomials of a set of degree-d polynomials. The bound is useful to us in our proof.
Lemma 2.1 (Kayal [16]). Let F be a field and let Q = {Q1 , Q2 , . . . , Qt } be a set of polynomials of
degree-d in N variables over the field F having algebraic rank k. Then there exists a Q-annihilating
polynomial of degree at most (k + 1) · d k .
2.3 Complexity of homogeneous components
We start by defining the homogeneous components of a polynomial.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 12
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
Definition 2.2. For a polynomial P and a positive integer i, we represent by Homi [P], the homogeneous
component of P of degree equal to i. By extension, we define Hom≤i [P] and Hom≥i [P] as follows.
i
Hom≤i [P] ≡ ∑ Hom j [P] .
j=0
deg(P)
Hom≥i [P] ≡ ∑ Hom j [P] .
j=i
We define Hom[P] as the ordered tuple of homogeneous components of P, i. e.,
Hom[P] ≡ Homd [P], Homd−1 [P], . . . , Hom0 [P] ,
where d is the degree of P.
We will use the following simple lemma whose proof is fairly standard using interpolation, and can
be found in the paper [28], for instance. We sketch the proof here for completeness.
Lemma 2.3. Let F be a field of characteristic zero, and let P ∈ F[X1 , X2 , . . . , XN ] be a polynomial of
degree at most d, in N variables, such that P can be represented as
P = C(Q1 , Q2 , . . . , Qt ) ,
where for every j ∈ [t], Q j is a polynomial in N variables, and C is an arbitrary polynomial in t variables.
Then, there exist polynomials {Q0i j : i ∈ [d + 1], j ∈ [t]}, and for every ` such that 0 ≤ ` ≤ d, there exist
0 ,C 0 , . . . ,C 0
polynomials C`,1 `,2 `,d+1 satisfying
(d+1)
0
Hom` [P] = ∑ C`,i (Q0i1 , Q0i2 , . . . , Q0it ) .
i=1
Moreover,
• if each of the polynomials in the set {Q j : j ∈ [t]} is of degree at most ∆, then every polynomial in
the set {Q0i j : i ∈ [d + 1], j ∈ [t]} is also of degree at most ∆;
• if the algebraic rank of the set {Q j : j ∈ [t]} of polynomials is at most k, then for every i ∈ [d + 1],
the algebraic rank of the set {Q0i j : j ∈ [t]} of polynomials is also at most k.
Proof. The key idea is to start from P ∈ F[X] and obtain a new polynomial P0 ∈ F[X][Z] such that for
every ` such that 0 ≤ ` ≤ d, the coefficient of Z ` in P0 equals Hom` [P]. Here, Z is a new variable. Such
a P0 is obtained by replacing every occurrence of the variable X j (for each j ∈ [N]) in P by Z · X j . It is
not hard to verify that such a P0 has the stated property. We now view P0 as a univariate polynomial in Z
with the coefficients coming from F(X). Notice that the degree of P0 in Z is at most d. So, to recover the
coefficients of a univariate polynomial of degree at most d, we can evaluate P0 at d + 1 distinct values of
Z over F(X) and take an F(X) linear combination. In fact, if the field F is large enough, we can assume
that all these distinct values of Z lie in the base field F and we only take an F linear combination. The
properties in the “moreover” part of the lemma immediately follow from this construction, and we skip
the details.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 13
M RINAL K UMAR AND S HUBHANGI S ARAF
2.4 Roots of polynomials
We will crucially use the following result of Dvir, Shpilka, Yehudayoff [8].
Lemma 2.4 (Lemma 3.1 in Dvir, Shpilka, Yehudayoff [8]). For a field F, let P ∈ F[X1 , X2 , . . . , XN ,Y ]
be a non-zero polynomial of degree at most k in Y . Let f ∈ F[X1 , X2 , . . . , XN ] be a polynomial such that
∂P
P(X1 , X2 , . . . , XN , f ) = 0 and ∂Y (0, 0, . . . , 0, f (0, 0, . . . , 0)) 6= 0. Let
k
P = ∑ Ci (X1 , X2 , . . . , XN ) ·Y i .
i=0
Then, for every t ≥ 0, there exists a polynomial Rt ∈ F[Z1 , Z2 , . . . , Zk+1 ] of degree at most t such that
Hom≤t [ f (X1 , X2 , . . . , XN )] = Hom≤t [Rt (C0 ,C1 , . . . ,Ck )] . (2.1)
We also use the following standard result about zeroes of polynomials.
Lemma 2.5 (Schwartz, Zippel, DeMillo, Lipton [5]). Let P be a non-zero polynomial of degree-d in N
variables over a field F. Let S be an arbitrary subset of F, and let x1 , x2 , . . . , xN be random elements from
S chosen independently and uniformly at random. Then
d
Pr[P(x1 , x2 , . . . , xN ) = 0] ≤ .
|S|
The following corollary easily follows from the lemma above.
Corollary 2.6. Let P1 , P2 , . . . , Pt be non-zero polynomials of degree-d in N variables over a field F. Let
S be an arbitrary subset of F of size at least 2td, and let x1 , x2 , . . . , xN be random elements from S chosen
independently and uniformly at random. Then
1
Pr[∀i ∈ [t], Pi (x1 , x2 , . . . , xN ) 6= 0] ≥ .
2
2.5 Approximations
We will use the following lemma of Saptharishi [35] for numerical approximations in our calculations.
Lemma 2.7 (Saptharishi [35]). Let n and ` be parameters such that ` = (n/2)(1 − ε) for some ε = o(1).
√
For any a, b such that a, b = O( n),
n−a n
= · 2−a · (1 + ε)a−2b · exp(O(b · ε 2 )) .
`−b `
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 14
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
3 Utilizing low algebraic rank
Let Q = {Q1 , Q2 , . . . , Qt } be a set of polynomials in N variables and degree at most d such that the
algebraic rank of Q equals k. Without loss of generality, let us assume that B = {Q1 , Q2 , . . . , Qk } are an
algebraically independent subset of C of maximal size. We now show that, in some sense, this implies
that all the polynomials in Q can be represented as functions of polynomials in the set B. We make this
notion formal in the lemma below, which is a restatement of Lemma 1.10.
Lemma 3.1 (Lemma 1.10 restated). Let F be any field of characteristic zero or sufficiently large. Let
Q = {Q1 , Q2 , . . . , Qt } be a set of polynomials in N variables such that the algebraic rank of Q equals k.
Let di = deg(Qi ) (i ∈ [t]) and let B = {Q1 , Q2 , . . . , Qk } be a maximal algebraically independent subset of
Q. Then, there exists an a = (a1 , a2 , . . . , aN ) in FN and polynomials Fk+1 , Fk+2 , . . . , Ft in k variables such
that ∀i ∈ {k + 1, k + 2, . . . ,t}
Qi (X + a) = Hom≤di Fi (Q1 (X + a), Q2 (X + a), . . . , Qk (X + a)) .
Proof. Let d be defined as maxi {di }. Let us consider any i such that i ∈ {k + 1, k + 2, . . . ,t}. From the
statement of the lemma, it follows that the set of polynomials in the set B ∪ {Qi } are algebraically depen-
dent. Therefore, there exists a nonzero polynomial Ai in k + 1 variables such that Ai (Q1 , Q2 , . . . , Qk , Qi ) ≡
0. Without loss of generality, we choose such a polynomial with the smallest total degree. From the upper
bound on the degree of the annihilating polynomial from Lemma 2.1, we can assume that the degree of
Ai is at most (k + 1)d k . Consider the polynomial A0i (X,Y ) defined by
A0i (X,Y ) = Ai (Q1 (X), Q2 (X), . . . , Qk (X),Y ) .
We have the following observation about properties of A0i .
Observation 3.2. A0i satisfies the following conditions.
• A0i is not identically zero.
• The Y degree of A0i is at least one.
• Qi (X) is a root of the polynomial A0i , when viewing it as a polynomial in the Y variable with
coefficients coming from F(X).
Proof. We prove the items in sequence.
• If A0i is identically zero, then it follows that Q1 , Q2 , . . . , Qk are algebraically dependent, which is a
contradiction.
• If A0i (X,Y ) does not depend on the variable Y , then by definition, it follows that Ai (Q1 , Q2 , . . . , Qk ,Y )
does not depend on Y . Hence, Ai (Q1 , Q2 , . . . , Qk , Qi ) does not depend on Qi but is identically zero.
This contradicts the algebraic independence of Q1 , Q2 , . . . , Qk .
• This item follows from the fact that the polynomial obtained by substituting Y by Qi in A0i equals
Ai (Q1 , Q2 , . . . , Qk , Qi ), which is identically zero.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 15
M RINAL K UMAR AND S HUBHANGI S ARAF
Our aim now is to invoke Lemma 2.4 for the polynomial A0i , but first, we need to verify that the
conditions in the hypothesis of Lemma 2.4 are satisfied. Let the polynomial A00i be defined as the first
order derivative of A0i with respect to Y . Formally,
∂ A0i
A00i =
.
∂Y
We proceed with the following claim, the proof of which we defer to the end.
Claim 3.3. The polynomial A00i is not an identically zero polynomial and A00i |Y =Qi is not identically zero.
For the ease of notation, we define
Li (X) = A00i |Y =Qi .
Observe that Li is a polynomial in the variables X which is not identically zero and is of degree at most
(k + 1)d k+1 . Let H be a subset of F of size 2t(k + 1)d k+1 . Then, for a uniformly random point ai picked
from H N , the probability that Li vanishes at ai is at most 1/2t. We call the set of all points ai ∈ H N where
Li vanishes as bad. Then, with a probability at least 1 − 1/2t, a uniformly random element of H N is not
bad. Let ai ∈ FN be a “not bad” element. We can replace X j by X j + γ, where γ is the jth coordinate of ai
and then for the resulting polynomial Li (X + ai ), the point (0, 0, . . . , 0) is not bad.
We are now ready to apply Lemma 2.4. Let
(k+1)d k
A0i (X,Y ) = ∑ C j (X) ·Y j .
j=0
Here, for every j, C j (X) = C0j Q1 (X), Q2 (X), . . . , Qk (X) is a polynomial in the X variables and is the
coefficient of Y j in A0i (X,Y ) when viewed as an element of F[X][Y ]. From the discussion above, we know
that the following are true.
1. The polynomial A0i (X + ai , Qi (X + ai )) is identically zero.
2. The first derivative of A0i (X + ai ,Y ) with respect to Y does not vanish at (0, 0, . . . , 0, Qi (0, 0, . . . , 0)).
Therefore, by Lemma 2.4, it follows that there is a polynomial Gi such that
h i
Qi (X + ai ) = Hom≤di Gi (C0 (X + ai ),C1 (X + ai ), . . . ,C(k+1)d k (X + ai )) .
We also know that for every j ∈ {0, 1, . . . , (k + 1)d k }, C j (X + ai ) is a polynomial in the polynomials
Q1 (X + ai ), Q2 (X + ai ), . . . , Qk (X + ai ). In other words,
Qi (X + ai ) = Hom≤di Fi (Q1 (X + ai ), Q2 (X + ai ), . . . , Qk (X + ai ))
for a polynomial Fi .
In order to prove the lemma for all values of i ∈ {k + 1, k + 2, . . . ,t}, we observe that we can pick
a single value of the translation a, which works for every i ∈ {k + 1, k + 2, . . . ,t}. Such an a exists
because the probability that a uniformly random p ∈ H N is bad for some i is at most t · 1/2t = 1/2 and
the translation corresponding to any such element a in H N which is not bad for every i will work. The
statement of the lemma then immediately follows.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 16
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
We now prove Claim 3.3.
Proof of Claim 3.3. We observed from the second item in Observation 3.2 that the degree of Y in A0i
is at least 1. Hence, A00i is not identically zero. If A00i |Y =Qi is identically zero, then it follows that
{Q1 , Q2 , . . . , Qk , Qi } have an annihilating polynomial of degree smaller than the degree of Ai , which is a
contradiction to the choice of Ai , as a minimum degree annihilating polynomial.
Lemma 3.1 lets us express all polynomials in a set of polynomials as a function of the polynomials in
the transcendence basis. However, the functional form obtained is slightly cumbersome for us to use in
our applications. We now derive the following corollary, which is easier to use in our applications.
Corollary 3.4. Let F be any field of characteristic zero or sufficiently large. Let Q = {Q1 , Q2 , . . . , Qt }
be a set of polynomials in N variables such that the for every i ∈ [t], the degree of Qi is equal to di < d
and the algebraic rank of Q equals k. Let B = {Q1 , Q2 , . . . , Qk } be a maximal algebraically independent
subset of Q. Then, there exists an a = (a1 , a2 , . . . , aN ) in FN and polynomials Fk+1 , Fk+2 , . . . , Ft in at most
k(d + 1) variables such that ∀i ∈ {k + 1, k + 2, . . . ,t}
Qi (X + a) = Fi (Hom[Q1 (X + a)], Hom[Q2 (X + a)], . . . , Hom[Qk (X + a)]) .
Proof. Let i be such that i ∈ {k + 1, k + 2, . . . ,t}. From Lemma 3.1, we know that there exists an a ∈ FN
and a polynomial Wi such that
Qi (X + a) = Hom≤di Wi (Q1 (X + a), Q2 (X + a), . . . , Qk (X + a)) .
(3.1)
We will now show that Hom≤di Wi (Q1 (X + a), Q2 (X + a), . . . , Qk (X + a)) is actually a polynomial in
the homogeneous components of the various Q j (X + a) by the following procedure, which is essentially
univariate polynomial interpolation.
• Let R(X) = Wi (Q1 (X + a), Q2 (X + a), . . . , Qk (X + a)). We replace every variable X j in R by Z · X j
for a new variable Z. We view the resulting polynomial R0 as an element of F(X)[Z], i. e., a
univariate polynomial in Z with coefficients coming from the field of rational functions in the X
variables.
• Now, observe that for any `, the homogeneous component of degree-` of R is precisely the
coefficient of Z ` in R0 . Hence, we can evaluate R0 for sufficiently many distinct values of Z in
F(X), and then take an F(X) linear combination of these evaluations to express the homogeneous
components. Moreover, since F is an infinite field, without loss of generality, we can pick the
values of Z to be scalars in F, and in this case, we will just be taking an F linear combination.
The catch here is that after replacing X j by Z ·X j and substituting different values of Z ∈ F, the polynomials
Qi0 (X + a) could possibly lead to distinct polynomials. In general, this is bad, since our goal is to show
that every polynomial in a set of algebraically dependent polynomials in a function of few polynomials.
However, the following observation comes to our rescue. Let P be any polynomial in F[X] of degree-∆
and let P0 be the polynomial obtained from P by replacing X j by Z · X j . Then,
∆
P0 (X + a) = ∑ Z ` · Hom` [P(X + a)] . (3.2)
`=0
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 17
M RINAL K UMAR AND S HUBHANGI S ARAF
In particular, the set of polynomials obtained from P0 for different values of Z are all in the linear span of
homogeneous components of P.
Therefore, any homogeneous component of R can be expressed as a function of the set
k
[
Hom Qi (X + a)
i=1
of polynomials. This completes the proof of the corollary.
We now prove the following lemma, which will be directly useful in the our applications to polynomial
identity testing and lower bounds in the following sections.
Lemma 3.5. Let F be any field of characteristic zero or sufficiently large. Let P ∈ F[X] be a polynomial
in N variables, of degree equal to n, such that P can be represented as
T
P = ∑ Fi (Qi1 , Qi2 , . . . , Qit )
i=1
and such that the following are true.
• For each i ∈ [T ], Fi is a polynomial in t variables.
• For each i ∈ [T ] and j ∈ [t], Qi j is a polynomial in N variables of degree at most d.
• For each i ∈ [T ], the algebraic rank of the set {Qi j : j ∈ [t]} of polynomials is at most k and
Bi = {Qi1 , Qi2 , . . . , Qik } is a maximal algebraically independent subset of {Qi j : j ∈ [t]}.
Then, there exists an a ∈ FN and polynomials Fi0 in at most k(d + 1) variables such that
T
P(X + a) = ∑ Fi0 (Hom[Qi1 (X + a)], Hom[Qi2 (X + a)], . . . , Hom[Qik (X + a)]) .
i=1
Proof. The proof would essentially follow from the application of Corollary 3.4 to each of the summands
on the right hand side. The only catch is that the translations a could be different for each one of them.
Since we are working over infinite fields, without loss of generality, we can assume that there is a good
translation a which works for all the summands.
4 Application to lower bounds
In this section , we prove Theorem 1.5. But, first we discuss the definitions of the complexity measure
used in the proof, the notion of random restrictions and the family of hard polynomials that we work with.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 18
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
4.1 Projected shifted partial derivatives
The complexity measure that we use to prove the lower bounds in this paper is the notion of projected
shifted partial derivatives of a polynomial introduced by Kayal et al. in [18] and subsequently used in a
number of following papers [29, 19, 28].
For a polynomial P and a monomial γ, ∂∂ Pγ is the partial derivative of P with respect to γ and for a set
of monomials M, ∂M (P) is the set of partial derivatives of P with respect to monomials in M. The space
of (M, m)-projected shifted partial derivatives of a polynomial P is defined below.
Definition 4.1 ((M, m)-projected shifted partial derivatives). For an N-variate polynomial
P ∈ F[X1 , X2 , . . . , XN ] ,
set of monomials M and a positive integer m ≥ 0, the space of (M, m)-projected shifted partial derivatives
of P is defined as
( " # )
def
h∂M (P)im = F- span Mult ∏ Xi · g : g ∈ ∂M (P), S ⊆ [N], |S| = m . (4.1)
i∈S
Here, Mult[P] of a polynomial P is the projection of P on the multilinear monomials in its support. We
use the dimension of projected shifted partial derivative space of P with respect to some set of monomials
M and a parameter m as a measure of the complexity of a polynomial. Formally,
ΦM,m (P) = Dim(h∂M (P)im ) .
From the definitions, it is straightforward to see that the measure is subadditive.
Lemma 4.2 (Subadditivity). Let P and Q be any two multivariate polynomials in F[X1 , X2 , . . . , XN ]. Let
M be any set of monomials and m be any positive integer. Then, for all scalars α and β
ΦM,m (α · P + β · Q) ≤ ΦM,m (P) + ΦM,m (Q) .
In the proof of Theorem 1.5, we need to upper bound the dimension of the span of projected shifted
partial derivatives of the homogeneous component of a fixed degree of polynomials. The following
lemma comes to our rescue there.
Lemma 4.3. Let P be a polynomial of degree at most d. Then for every 0 ≤ i ≤ d, and for every choice
of parameters m, r and a set M of monomials of degree equal to r, the following inequality is true.
φM,m (P) ≥ φM,m (Homi [P]) .
Proof. Since M is a subset of monomials of degree equal to r, all the partials derivatives are shifted
by monomials of degree equal to m and the operation Mult[] either sets a monomial to zero or leaves
it unchanged, it follows that the span of projected shifted partial derivatives of Homi [P] coincides with
the span of the homogeneous components of degree-(i − r)m in the space of span of projected shifted
partial derivatives of P itself. The lemma then follows from the fact that dimension of a linear space of
polynomials is at least as large as the dimension of the space obtained by restricting all polynomials to
some fixed homogeneous component.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 19
M RINAL K UMAR AND S HUBHANGI S ARAF
In the next lemma, we prove an upper bound on the polynomials which are obtained by a composition
of low arity polynomials with polynomials of small support. Gupta et al. [13] first proved such a bound
for homogeneous depth-4 circuit with bounded bottom fan-in.
Lemma 4.4. Let s be a parameter and Q1 , Q2 , . . . , Qt be polynomials in F[X] such that for every i ∈ [t],
the support of every monomial in Qi is of size at most s. Then, for every polynomial F in t variables,
every choice of parameters r, m such that m + rs ≤ N/2, and every set M of monomials of degree equal
to r,
t +r N
ΦM,m (F(Q1 , Q2 , . . . , Qt )) ≤ N · · .
r m + rs
Proof. By the chain rule for partial derivatives, every derivative of order r of F(Q1 , Q2 , . . . , Qt ) can be
written as a linear combination of products of the form
∂ F(Y1 ,Y2 , . . . ,Yt ) ∂ Pj
|Yi =Qi · ∏
∂ β0 1≤ j≤r0 ∂ β j
where
1. r0 is at most r,
2. β0 is a monomial in variables Y1 ,Y2 , . . . ,Yt of degree at most r,
3. for every 1 ≤ j ≤ r, the polynomial Pj is an element of {Q1 , Q2 , . . . , Qt }, and
4. for every 1 ≤ j ≤ r, β j is a monomial in variables X1 , X2 , . . . , XN .
Since every monomial in each Qi is of support at most s, every monomial in each of the products
∂ Pj
∏ ∂βj
1≤ j≤r
is of support at most rs. Therefore, for shifts of degree- m, the projected shifted partial derivatives
of F(Q1 , Q2 , . . . , Qt ) (with respect to monomials in M which are of degree-r) are in the linear span of
polynomials of the form
∂ F(Y1 ,Y2 , . . . ,Yt )
Mult |Yi =Qi · α
∂ β0
where α is a multilinear monomial14 of degree at most m + rs. Therefore, the dimension of this space is
upper bounded by the number of possible choices of β0 and α. Hence
t +r N
ΦM,m (F(Q1 , Q2 , . . . , Qt )) ≤ N · · .
r m + rs
14 If α is not multilinear, the term is set to zero.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 20
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
4.2 Target polynomials for the lower bound
In this section, we define the family of polynomials for which we prove our lower bounds. The family
is a variant of the Nisan-Wigderson polynomials which were introduced by Kayal et al. in [20], and
subsequently used in many other results [29, 19, 28]. We start with the following definition.
Definition 4.5 (Nisan-Wigderson polynomial families). Let n, q, e be arbitrary parameters with q being
a power of a prime, and n, e ≤ q. We identify the set [q] with the field Fq of q elements. Observe that
since n ≤ q, we have that [n] ⊆ Fq . The Nisan-Wigderson polynomial with parameters n, q, e, denoted by
NWn,q,e is defined as
NWn,q,e (X) = ∑ X1,p(1) . . . Xn,p(n) .
p(t)∈Fq [t]
deg(p)<e
The number of variables in NWn,q,e as defined above is N = q · n. The lower bounds in this paper will
be proved for the polynomial NW ◦ Lin which is a variant of the polynomial NWn,q,e defined as follows.
Definition 4.6 (Hard polynomials for the lower bound). Let δ ∈ (0, 1) be an arbitrary constant, and let
p = N −δ . Let
N
γ = = N 1+δ .
p
The polynomial NW ◦ Linq,n,e,p is defined as
!
γ γ γ
NW ◦ Linq,n,e,p = NWq,n,e ∑ X1,1,i , ∑ X1,2,i , . . . , ∑ Xn,q,i .
i=1 i=1 i=1
For brevity, we will denote NW ◦ Linq,n,e,p by NW ◦ Lin for the rest of the discussion. The advantage
of using this trick15 of composing with linear forms is that it becomes cleaner to show that the polynomial
NW ◦ Lin is robust under random restrictions where every variable is kept alive with a probability p.
Since δ is an absolute constant, the number of variables in NW ◦ Lin is at most N O(1) . We now formally
define our notion of random restrictions.
Let V be the set of variables in the polynomial NW ◦ Lin. We now define a distribution D p over the
subsets of V.
The distribution D p : Each variable in V is independently kept alive with a probability p = N −δ .
The random restriction procedure samples a V ← D and then keeps only the variables in V alive. The
remaining variables are set to 0. We denote the restriction of the polynomial obtained by such a restriction
as NW ◦ Lin|V . Observe that a random restriction also results in a distribution over the restrictions of a
circuit computing the polynomial NW ◦ Lin. We denote by C|V the restriction of a circuit C obtained by
setting every input gate in C which is labeled by a variable outside V to 0.
We now show that with a high probability over restrictions sampled according to D p , the projected
shifted partial derivative complexity of NW ◦ Lin remains high. We need the following lower bound on
the dimension of projected shifted partial derivatives of NWn,q,e .
15 This idea came up during discussions with Ramprasad Saptharishi.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 21
M RINAL K UMAR AND S HUBHANGI S ARAF
√
Lemma 4.7 ([29, 25]). For every n and r = O( n) there exists parameters q, e, ε such that q = Ω(n2 ),
√
N = qn and ε = Θ(log(n)/ n) with
qr ≥ (1 + ε)2(n−r) ,
n−r
2
qe−r = · Poly(q) .
1+ε
For any {n, q, e, r, ε} satisfying the above constraints, and for m = (N/2)(1 − ε), over any field F, we
have
N
Φ(NWn,q,e ) ≥ · exp(−O(log2 n)) .
m+n−r
We will instantiate the lemma above with the following choice of parameters.
• ε = 4√
log n
n
,
√
• r= n,
• q = n10 .
√
• We will set the parameter s to be equal to 100n .
It is straightforward to check that for the above choice of parameters, there is a choice of e such that
qr ≥ (1 + ε)2(n−r) ,
n−r
e−r 2
q = · Poly(q) .
1+ε
Therefore, for m = (N/2)(1 − ε), over any field F, we have
N
Φ(NWn,q,e ) ≥ · exp(−O(log2 n)) .
m+n−r
We are now ready to prove our main lemma for this section.
Lemma 4.8. With a probability at least 1 − o(1) over V ← D p , there exists a subset of variables V 0 ⊆ V
such that |V 0 | = N and
N
Φ(NW ◦ Lin|V 0 ) ≥ · exp(−O(log2 n)) .
m+n−r
Proof. To prove the lemma, we first show that with a high probability over the random restrictions, the
polynomial P|V has the polynomial NWn,q,e as a projection by setting some variables to zero. Combining
this with Lemma 4.7 would complete the proof. We now fill in the details.
Let i ∈ [N]. Then, the probability that all the variables in the set Ai, j = {Xi, j,` : ` ∈ [γ]} are set to zero
by the random restrictions is equal to (1 − p)γ ≤ exp(−Θ(N)). Therefore, the probability that there exists
an i ∈ [n], j ∈ [q] such that all the variables in the set Ai, j are set to zero by the random restrictions, is at
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 22
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
most N · exp(−Θ(N)) = o(1). We now argue that if this event does not happen (which is the case with
probability at least 1 − o(1)), then the dimension of the projected shifted partial derivatives is large.
For every i, j, let A0i, j be the subset of Ai, j which has not been set to zero. We know that for every i, j,
A0i, j is non-empty. Now, for every i, j, we set all the elements of A0i, j to zero except one. Observe that
the polynomial obtained from NW ◦ Lin after this restriction is exactly the polynomial NWn,q,e up to a
relabeling of variables. Now, from Lemma 4.7, our claim follows.
4.3 Proof of Theorem 1.5
To prove our lower bound, we show that under a random restriction from the distribution D p , the
dimension of the linear span of projected shifted partial derivatives of any ΣΠ(n) ΣΠ circuit C is small
with a high probability if the size of the C is not too large. Comparing this with the lower bound on
the dimension of projected shifted partials of the polynomial NW ◦ Lin under random restrictions from
Lemma 4.8, the lower bound follows. We now proceed along this outline and prove the following lemma.
Lemma 4.9 (Upper bound on complexity of circuits). Let m, r, s be parameters such that m + rs ≤ N/2.
Let M be any set of multilinear monomials of degree-r. Let C be an arithmetic circuit computing a
homogeneous polynomial of degree-n such that
T
C = ∑ Ci (Qi1 , Qi2 , . . . , Qit )
i=1
where
• for each i ∈ [T ], Ci is a polynomial in t variables, and
• for each i ∈ [T ], the algebraic rank of the set {Qi j : j ∈ [t]} of polynomials is at most k.
For each i ∈ [T ] and j ∈ [t], let Si j be the set of monomials with nonzero coefficients in Qi j . If
[ δs
Si j ≤ N 2
i∈[T ], j∈[t]
then, with a probability at least 1 − o(1) over V ← D p 16 for all subsets V 0 of V of size at most N
k(n + 1) + r N
Φ(C|V 0 ) ≤ T N .
r m + rs
Proof. We prove the lemma by first using random restrictions to simplify the circuit into one with
bounded bottom support, and then utilizing the tools tools developed in Section 3 and Section 4.1 to
conclude that the dimension of the space of projected shifted partial derivatives of the resulting circuit is
small.
16 This is the distribution defined in Section 4.2, where every variable is kept alive with a probability N −δ for a constant
δ ∈ (0, 1).
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 23
M RINAL K UMAR AND S HUBHANGI S ARAF
Step (1): Random restrictions. From the definition of random restrictions, every variable is kept alive
independently with a probability p = N −δ . So, the probability that a monomial of support at least s
survives the restrictions is at most N −δ s . Therefore, by linearity of expectations, the expected number of
S
monomials of support at least s in i∈[T ], j∈[t] Si j which survive the random restrictions is at most
δs
Si j · N −δ s ≤ N − 2 .
[
i∈[T ], j∈[t]
S
So, by Markov’s inequality, the probability that at least one monomial of support at least s in i∈[T ], j∈[t] Si j
survives the random restrictions is o(1). Let V 0 be any subset of the surviving set of variables of size N.
For the rest of the proof, we assume that all the variables outside the set V 0 are set to zero. Restrictions
S
which set all monomials of support at least s in i∈[T ], j∈[t] Si j to zero are said to be good.
Step (2): Using low algebraic rank. In this step, we assume that we are given a good restriction C0 of
the circuit C. Let
T
C0 = ∑ Ci0 (Q0i1 , Q0i2 , . . . , Q0it )
i=1
where for every i ∈ [T ], j ∈ [t], all monomials of Q0i j have support at most s. Observe that random
restrictions cannot increase the algebraic rank of a set of polynomials. Therefore, for every i ∈ [T ], the
algebraic rank of the set {Q0i j : j ∈ [t]} of polynomials is at most k. For ease of notation, let us assume
that the algebraic rank is equal to k. Without loss of generality, let the set Bi = {Q0i1 , Q0i2 , . . . , Q0ik } be the
set guaranteed by Lemma 3.5. We know that there exists an a ∈ FN and polynomials {Fi0 : i ∈ [T ]} such
that
T
C0 (X + a) = ∑ Fi0 (Hom Q0i1 (X + a) , Hom Q0i2 (X + a) , . . . , Hom Q0ik (X + a) ) .
(4.2)
i=1
Moreover, since C(X) (and hence C0 (X)) is a homogeneous polynomial of degree-n, the following is true.
" #
T
0
Fi0 (Hom
n
0 0 0
C (X) = Hom ∑ Qi1 (X + a) , Hom Qi2 (X + a) , . . . , Hom Qik (X + a) ) . (4.3)
i=1
An important observation here is that for the rest of the argument, we can assume that the degree of every
polynomial Q0i j (X + a) is at most n. If not, we can simply replace any such high degree Q0i j (X + a) by
Hom≤n Q0i j (X + a) .
We claim that the equality 4.3 continues to hold. This is because the higher degree monomials of Qi j
do not participate in the computation of the lower degree monomials. The only monomials which could
potentially change by this substitution are the ones with degree strictly larger than n.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 24
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
Step (3): Upper bound on ΦM,m (C0 (X)). Let R be defined the polynomial
T
R = ∑ Fi0 (Hom Q0i1 (X + a) , Hom Q0i2 (X + a) , . . . , Hom Q0ik (X + a) ) .
(4.4)
i=1
Note that if the support of every monomial in a polynomial Q0i j (X) is at most s, then for every translation
a ∈ FN the support of every monomial in Q0i j (X + a) is also at most s. From Lemma 4.4 and from
Lemma 4.2, it is easy to see that
k(n + 1) + r N
ΦM,m (R) ≤ T N .
r m + rs
From Lemma 4.3, it follows that
0 k(n + 1) + r N
ΦM,m (C (X)) ≤ ΦM,m (R) ≤ T N .
r m + rs
Observe that steps (2) and (3) of the proof are always successful if the restriction in step 1 is good, which
happens with a probability at least 1 − o(1). So, the lemma follows.
We now complete the proof of Theorem 1.5.
√
Proof of Theorem 1.5. √If the size of the circuit C is at least N (δ /2) n , then we are done. Else, the size
of C is at most N (δ /2) n .√This implies that the total number of monomials in all the polynomials Qi j
together is at most N (δ /2) n . From Lemma 4.9 and Lemma 4.8, it follows that there exists a subset V 0 of
variables of size N such that both the following inequalities are true.
k(n + 1) + r N
ΦM,m (C|V 0 ) ≤ T N (4.5)
r m + rs
and
N
ΦM,m (NW ◦ Lin|V 0 ) ≥ · exp(− log2 n) . (4.6)
m+n−r
Since C computes NW ◦ Lin, it must be the case that
N 2
m+n−r · exp(− log n)
T≥ N .
N k(n+1)+r
r m+rs
Plugging in the value of the parameters from Section 4.2, and approximating using Lemma 2.7, we
immediately get
N N
= · (1 + ε)2(n−r) · exp(O((n − r) · ε 2 ))
m+n−r m
and
N N
= · (1 + ε)2rs · exp(O(rs · ε 2 )) .
m + rs m
√
Moreover, k(n+1)+r
r ≤ (enk)r ≤ exp(2 n · log n). Taking the ratio and substituting the values of the
parameters, we get √
T ≥ exp (Ω( n log N)) .
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 25
M RINAL K UMAR AND S HUBHANGI S ARAF
5 Application to polynomial identity testing
In this section we give an application of the ideas developed in Section 3 to the question of polynomial
identity testing and prove Theorem 1.8. We start by formally defining the notion of a hitting set.
Hitting set. Let S be a set of polynomials in N variables over a field F. Then, a set H ⊆ FN is said to
be a hitting set for the class S, if for every polynomial P ∈ S such that P is not identically zero, there
exists a p ∈ H such that P(p) 6= 0.
For our PIT result, we show that any nonzero polynomial P in the circuit class we consider, has a
monomial of low support. A hitting set can then be constructed by the standard techniques using the
Shpilka-Volkovich generator [40].
Lemma 5.1 (Shpilka-Volkovich generator [40]17 ). Let F be a field of characteristic zero. For every
`, d, N, there exists a set H ⊆ FN of size at most (O(Nd))` such that for every nonzero polynomial P of
degree at most d in N variables which contains a monomial of support at most `, there exists an h ∈ H
such that P(h) 6= 0. Moreover, the set H can be constructed in time Poly(N, d, `) · (O(Nd))` .
The following lemma is our main technical claim.
Lemma 5.2. Let F be a field of characteristic zero. Let P be a homogeneous polynomial of degree-∆ in
N variables such that P can be represented as
T
P = ∑ Ci (Qi1 , Qi2 , . . . , Qit )
i=1
such that the following are true.
• For each i ∈ [T ], Ci is a polynomial in t variables.
• For each i ∈ [T ] and j ∈ [t], Qi j is a polynomial of degree at most d in N variables.
• For each i ∈ [T ], the algebraic rank of the set {Qi j : j ∈ [t]} of polynomials is at most k.
Then, the trailing monomial of P has support at most
2e3 d · (ln (T (∆ + 1)) + (d + 1)k ln (2(d + 1)k) + 1) .
Here, e is Euler’s constant.
In order to prove Lemma 5.2, we follow the outline of proving robust lower bounds for arithmetic
circuits, described and used by Forbes [9]. This essentially amounts to showing that the trailing monomial
of P has small support. We use the following result of Forbes [9] in a blackbox manner which greatly
simplifies our proof.
17 See Corollary 3.15 in [9].
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 26
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
Lemma 5.3 (Proposition 4.18 in Forbes [9]). Let R(X) be a polynomial in F[X] such that
T
R(X) = ∑ Fi (Qi1 , Qi2 , . . . , Qit )
i=1
and for each i ∈ [T ] and j ∈ [t], the degree of Qi j is at most d. Let α be the trailing monomial of R. Then,
the support of α is at most 2e3 d(ln T + t ln 2t + 1), where e is Euler’s constant.
We now proceed to prove Lemma 5.2.
Proof of Lemma 5.2. Recall that our goal is to show that the polynomial P, which can be represented as
T
P = ∑ Ci (Qi1 , Qi2 , . . . , Qit ) ,
i=1
has a trailing monomial of small support.
For every i ∈ [T ], let Qi = {Qi1 , Qi2 , . . . , Qit } and let Qi be of algebraic rank ki . Without loss of
generality, let us assume the sets Bi = {Qi1 , Qi2 , . . . , Qiki } are the sets guaranteed by Lemma 3.5. This
implies that there exist polynomials F1 , F2 , . . . , FT and a ∈ FN such that
" #
T
P(X + a) = ∑ Fi (Hom[Qi1 (X + a)], Hom[Qi2 (X + a)], . . . , Hom[Qik (X + a)]) .
i (5.1)
i=1
Since each ki ≤ k, for the ease of notation, we assume that each ki = k. Observe that if P is a homogeneous
polynomial of degree deg(P) ≤ ∆, then,
Homdeg(P) [P(X + a)] ≡ P(X) .
So, from Lemma 2.3, it follows that there exist k(d + 1)-variate polynomials F10 , F20 , . . . , FT0 (∆+1) and a set
{Q0i j : i ∈ [T (∆ + 1)], j ∈ [k]} of polynomials such that
T (∆+1)
P(X) = ∑ Fi0 (Hom[Q0i1 (X + a)], Hom[Q0i2 (X + a)], . . . , Hom[Q0ik (X + a)]) .
i=1
Moreover, every polynomial in the set {Q0i j : i ∈ [T (∆+1)], j ∈ [k]} has degree at most d. Now, Lemma 5.3
implies that the trailing monomial α of P(X) has support at most
2e3 d · (ln (T (∆ + 1)) + (d + 1)k ln (2(d + 1)k) + 1) .
We are now ready to complete the proof of Theorem 1.8.
Proof of Theorem 1.8. From Definition 1.2, it follows there could be non-homogeneous polynomials
P ∈ C. So, we cannot directly use Lemma 5.2 to say something about them, since the proof relies on
homogeneity. But, this is not a problem, since a polynomial is identically zero if and only if all its
homogeneous components are identically zero. Moreover, by applying Lemma 2.3 to every summand
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 27
M RINAL K UMAR AND S HUBHANGI S ARAF
feeding into the top sum gate of the circuit, we get that every homogeneous component of P18 can also be
computed by a circuit similar in structure to that of P at the cost of a blow up by a factor ∆ + 1 in the top
fan-in. We can then apply Lemma 5.2 to each of these homogeneous components to conclude that if P is
not identically zero, then it contains a monomial of support at most
2e3 d · (ln T (∆ + 1)2 + (d + 1)k ln (2(d + 1)k) + 1) .
Theorem 1.8 immediately follows by detecting the low support monomial using Lemma 5.2 and
Lemma 5.1.
6 Open questions
We conclude with some open questions.
• Prove the lower bounds in the paper for a polynomial in VP. We believe this is true, but it seems
that we need a strengthening of the bounds proved in [29]. In particular, it needs to be shown that
the lower bound for IMM (Iterated matrix multiplication) continues to hold when a depth-4 circuit
is not homogeneous but the formal degree is at most the square of the degree of the polynomial
itself.
• It would be interesting to see if there are other applications of Lemma 1.10 to questions in
complexity theory. The Jacobian characterization of algebraic independence has several very
interesting applications [1, 6].
Acknowledgements
Many thanks to Ramprasad Saptharishi for answering numerous questions regarding the results and
techniques in [1]. We are also thankful to Michael Forbes for sharing a draft of his paper [9] with us and
to anonymous reviewers for comments which helped us in improving the presentation of the paper.
References
[1] M ANINDRA AGRAWAL , C HANDAN S AHA , R AMPRASAD S APTHARISHI , AND N ITIN S AXENA:
Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas and depth-3 transcen-
dence degree-k circuits. SIAM J. Comput., 45(4):1533–1562, 2016. Preliminary version in STOC
2012. [doi:10.1137/130910725, arXiv:1111.0582] 3, 4, 5, 8, 9, 10, 12, 28
[2] M ANINDRA AGRAWAL AND V. V INAY: Arithmetic circuits: A chasm at depth four. In Proc. 49th
FOCS, pp. 67–75. IEEE Comp. Soc. Press, 2008. Available at ECCC. [doi:10.1109/FOCS.2008.32]
2
18 Only the top fan-in increases by a factor of ∆ + 1, all other parameters in Definition 1.2 remain the same.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 28
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
[3] M ALTE B EECKEN , J OHANNES M ITTMANN , AND N ITIN S AXENA: Algebraic independence and
blackbox identity testing. Inform. and Comput., 222:2–19, 2013. Preliminary version in ICALP’11.
[doi:10.1016/j.ic.2012.10.004, arXiv:1102.2789] 5, 12
[4] X I C HEN , N EERAJ K AYAL , AND AVI W IGDERSON: Partial derivatives in arithmetic complexity and
beyond. Found. and Trends in Theoret. Comput. Sci., 6(1-2):1–138, 2011. [doi:10.1561/0400000043]
12
[5] R ICHARD A. D E M ILLO AND R ICHARD J. L IPTON: A probabilistic remark on algebraic program
testing. Inform. Process. Lett., 7(4):193–195, 1978. [doi:10.1016/0020-0190(78)90067-4] 14
[6] Z EEV DVIR , A RIEL G ABIZON , AND AVI W IGDERSON: Extractors and rank extractors for
polynomial sources. Comput. Complexity, 18(1):1–58, 2009. Preliminary version in FOCS’07.
[doi:10.1007/s00037-009-0258-4] 28
[7] Z EEV DVIR AND A MIR S HPILKA: Locally decodable codes with 2 queries and polynomial identity
testing for depth 3 circuits. SIAM J. Comput., 36(5):1404–1434, 2007. Preliminary version in
STOC’05. [doi:10.1137/05063605X] 3
[8] Z EEV DVIR , A MIR S HPILKA , AND A MIR Y EHUDAYOFF: Hardness-randomness tradeoffs for
bounded depth arithmetic circuits. SIAM J. Comput., 39(4):1279–1293, 2009. Preliminary version
in STOC’08. [doi:10.1137/080735850] 9, 11, 14
[9] M ICHAEL A. F ORBES: Deterministic divisibility testing via shifted partial derivatives. In Proc.
56th FOCS, pp. 451–465. IEEE Comp. Soc. Press, 2015. [doi:10.1109/FOCS.2015.35] 5, 8, 9, 11,
26, 27, 28
[10] M ICHAEL A. F ORBES AND A MIR S HPILKA: Quasipolynomial-time identity testing of non-
commutative and read-once oblivious algebraic branching programs. In Proc. 54th FOCS, pp.
243–252. IEEE Comp. Soc. Press, 2013. Available at ECCC. [doi:10.1109/FOCS.2013.34,
arXiv:1209.2408] 3
[11] D IMA G RIGORIEV AND M AREK K ARPINSKI: An exponential lower bound for depth 3 arithmetic
circuits. In Proc. 30th STOC, pp. 577–582. ACM Press, 1998. [doi:10.1145/276698.276872] 4
[12] D IMA G RIGORIEV AND A LEXANDER A. R AZBOROV: Exponential lower bounds for depth 3
arithmetic circuits in algebras of functions over finite fields. Appl. Algebra Eng. Commun. Comput.,
10(6):465–487, 2000. Preliminary version in FOCS’98. [doi:10.1007/s002009900021] 4
[13] A NKIT G UPTA , P RITISH K AMATH , N EERAJ K AYAL , AND R AMPRASAD S APTHARISHI: Ap-
proaching the chasm at depth four. J. ACM, 61(6):33:1–33:16, 2014. Preliminary versions in
CCC’13 and ECCC. [doi:10.1145/2629541] 2, 10, 20
[14] Z OHAR S HAY K ARNIN , PARTHA M UKHOPADHYAY, A MIR S HPILKA , AND I LYA VOLKOVICH: De-
terministic identity testing of depth-4 multilinear circuits with bounded top fan-in. SIAM J. Comput.,
42(6):2114–2131, 2013. Preliminary versions in STOC’10 and ECCC. [doi:10.1137/110824516] 3
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 29
M RINAL K UMAR AND S HUBHANGI S ARAF
[15] Z OHAR S HAY K ARNIN AND A MIR S HPILKA: Black box polynomial identity testing of general-
ized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica, 31(3):333–364, 2011.
Preliminary version in CCC’08. [doi:10.1007/s00493-011-2537-3] 3
[16] N EERAJ K AYAL: The complexity of the annihilating polynomial. In Proc. 24th IEEE
Conf. on Computational Complexity (CCC’09), pp. 184–193. IEEE Comp. Soc. Press, 2009.
[doi:10.1109/CCC.2009.37] 12
[17] N EERAJ K AYAL: An exponential lower bound for the sum of powers of bounded degree polynomials.
Electron. Colloq. on Comput. Complexity (ECCC), (81):1–5, 2012. Available at ECCC. 3
[18] N EERAJ K AYAL , N UTAN L IMAYE , C HANDAN S AHA , AND S RIKANTH S RINIVASAN: An exponen-
tial lower bound for homogeneous depth four arithmetic formulas. SIAM J. Comput., 46(1):307–335,
2017. Preliminary version in FOCS’14. [doi:10.1137/151002423] 3, 8, 10, 19
[19] N EERAJ K AYAL AND C HANDAN S AHA: Lower bounds for depth-three arithmetic circuits with
small bottom fanin. Comput. Complexity, 25(2):419–454, 2016. Preliminary versions in CCC’15
and ECCC. [doi:10.1007/s00037-016-0132-0] 19, 21
[20] N EERAJ K AYAL , C HANDAN S AHA , AND R AMPRASAD S APTHARISHI: A super-polynomial lower
bound for regular arithmetic formulas. In Proc. 46th STOC, pp. 146–153. ACM Press, 2014.
Available at ECCC. [doi:10.1145/2591796.2591847] 21
[21] N EERAJ K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS: An almost cubic lower bound
for depth three arithmetic circuits. In Proc. 43rd Internat. Colloq. on Automata, Languages and
Programming (ICALP’16), pp. 33:1–33:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik,
2016. Available at ECCC. [doi:10.4230/LIPIcs.ICALP.2016.33] 3
[22] N EERAJ K AYAL AND S HUBHANGI S ARAF: Blackbox polynomial identity testing for depth 3
circuits. In Proc. 50th FOCS, pp. 198–207. IEEE Comp. Soc. Press, 2009. Available at ECCC.
[doi:10.1109/FOCS.2009.67] 3
[23] N EERAJ K AYAL AND N ITIN S AXENA: Polynomial identity testing for depth 3 circuits. Comput.
Complexity, 16(2):115–138, 2007. Preliminary version in CCC 2016. [doi:10.1007/s00037-007-
0226-9] 3
[24] PASCAL KOIRAN: Arithmetic circuits: The chasm at depth four gets wider. Theoret. Comput. Sci.,
448:56–65, 2012. [doi:10.1016/j.tcs.2012.03.041, arXiv:1006.4700] 2
[25] M RINAL K UMAR AND R AMPRASAD S APTHARISHI: An exponential lower bound for homogeneous
depth-5 circuits over finite fields. Electron. Colloq. on Comput. Complexity (ECCC), (109):1–36,
2015. Available at ECCC. [arXiv:1507.00177] 22
[26] M RINAL K UMAR AND S HUBHANGI S ARAF: The limits of depth reduction for arithmetic formulas:
It’s all about the top fan-in. SIAM J. Comput., 44(6):1601–1625, 2015. Preliminary version in
STOC’14. [doi:10.1137/140999220, arXiv:1311.6716] 10
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 30
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
[27] M RINAL K UMAR AND S HUBHANGI S ARAF: Arithmetic circuits with locally low algebraic rank. In
Proc. 31st IEEE Conf. on Computational Complexity (CCC’16), pp. 34:1–34:27. Schloss Dagstuhl–
Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.34] 1
[28] M RINAL K UMAR AND S HUBHANGI S ARAF: Sums of products of polynomials in few variables:
lower bounds and polynomial identity testing. In Proc. 31st IEEE Conf. on Computational Complex-
ity (CCC’16), pp. 35:1–35:29. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. Available
at ECCC. [doi:10.4230/LIPIcs.CCC.2016.35, arXiv:1504.06213] 13, 19, 21
[29] M RINAL K UMAR AND S HUBHANGI S ARAF: On the power of homogeneous depth 4 arith-
metic circuits. SIAM J. Comput., 46(1):336–387, 2017. Preliminary version in FOCS’14.
[doi:10.1137/140999335, arXiv:1404.1950] 3, 8, 10, 19, 21, 22, 28
[30] R AFAEL O LIVEIRA , A MIR S HPILKA , AND B EN L EE VOLK: Subexponential size hitting sets
for bounded depth multilinear formulas. Comput. Complexity, 25(2):455–505, 2016. Preliminary
versions in ECCC and 10.4230/LIPIcs.CCC.2015.304CCC 2015. [doi:10.1007/s00037-016-0131-1,
arXiv:1411.7492] 3
[31] JAMES G. OXLEY: Matroid Theory. Oxford Univ. Press, 2006. 6
[32] A NURAG PANDEY, N ITIN S AXENA , AND A MIT S INHABABU: Algebraic independence over
positive characteristic: New criterion and applications to locally low algebraic rank circuits.
In 41st Internat. Symp. Mathemat. Found. Comput. Sci. (MFCS’16), pp. 74:1–74:15, 2016.
[doi:10.4230/LIPIcs.MFCS.2016.74] 9
[33] R AN R AZ: Elusive functions and lower bounds for arithmetic circuits. Theory of Computing,
6(7):135–177, 2010. Preliminary version in STOC’08. [doi:10.4086/toc.2010.v006a007] 3, 4
[34] R AMPRASAD S APTHARISHI: Recent progress on arithmetic circuit lower bounds. Bull. EATCS,
(114), 2014. 3
[35] R AMPRASAD S APTHARISHI: A survey of lower bounds in arithmetic circuit complexity, 2014.
Available at author’s GitHub. 3, 14
[36] S HUBHANGI S ARAF AND I LYA VOLKOVICH: Black-box identity testing of depth-4 multi-
linear circuits. In Proc. 43rd STOC, pp. 421–430. ACM Press, 2011. Available at ECCC.
[doi:10.1145/1993636.1993693] 3
[37] N ITIN S AXENA AND C. S ESHADHRI: From Sylvester-Gallai configurations to rank bounds:
Improved black-box identity test for deph-3 circuits. In Proc. 51st FOCS, pp. 21–29. IEEE Comp.
Soc. Press, 2010. [doi:10.1109/FOCS.2010.9] 3
[38] N ITIN S AXENA AND C. S ESHADHRI: Blackbox identity testing for bounded top-fanin depth-3
circuits: The field doesn’t matter. SIAM J. Comput., 41(5):1285–1298, 2012. Preliminary version in
STOC’11. [doi:10.1137/10848232] 3
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 31
M RINAL K UMAR AND S HUBHANGI S ARAF
[39] A MIR S HPILKA: Affine projections of symmetric polynomials. J. Comput. System Sci., 65(4):639–
659, 2002. Preliminary version in CCC’01. [doi:10.1016/S0022-0000(02)00021-1] 3
[40] A MIR S HPILKA AND I LYA VOLKOVICH: Read-once polynomial identity testing. Comput. Complex-
ity, 24(3):477–532, 2015. Preliminary version in RANDOM’09. [doi:10.1007/s00037-015-0105-8]
11, 26
[41] A MIR S HPILKA AND AVI W IGDERSON: Depth-3 arithmetic circuits over fields of char-
acteristic zero. Comput. Complexity, 10(1):1–27, 2001. Preliminary version in CCC’99.
[doi:10.1007/PL00001609] 3, 4
[42] A MIR S HPILKA AND A MIR Y EHUDAYOFF: Arithmetic circuits: A survey of recent results
and open questions. Found. and Trends in Theoret. Comput. Sci., 5(3-4):207–388, 2010.
[doi:10.1561/0400000039] 2
[43] S ÉBASTIEN TAVENAS: Improved bounds for reduction to depth 4 and depth 3. Inform. and Comput.,
240:2–11, 2015. Preliminary version in MFCS’13. [doi:10.1016/j.ic.2014.09.004, arXiv:1304.5777]
2
[44] L ESLIE G. VALIANT: Completeness classes in algebra. In Proc. 11th STOC, pp. 249–261. ACM
Press, 1979. [doi:10.1145/800135.804419] 2
AUTHORS
Mrinal Kumar
Rutgers University, New Brunswick, NJ
mrinalkumar08 gmail com
https://mrinalkr.bitbucket.io/
Shubhangi Saraf
Rutgers University, New Brunswick, NJ
shubhangi saraf gmail com
http://sites.math.rutgers.edu/~ss1984/
ABOUT THE AUTHORS
M RINAL K UMAR received his Ph. D. in Computer Science in May 2017 from Rutgers
University where he was advised by Swastik Kopparty and Shubhangi Saraf. His research
interests are in Arithmetic and Boolean circuit complexity and Error Correcting Codes.
Mrinal spent his undergrad years at IIT Madras and owes his interest in Complexity
Theory to a delightful class on the topic taught by Jayalal Sarma. Apart from theory, he
finds great joy in test cricket and in the adventures of Calvin & Hobbes.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 32
A RITHMETIC C IRCUITS WITH L OCALLY L OW A LGEBRAIC R ANK
S HUBHANGI S ARAF grew up in Pune, India. She received her Ph. D. in computer science
from the Massachusetts Institute of Technology in 2011 under the guidance of Madhu
Sudan. Shubhangi is broadly interested in complexity theory, coding theory and pseudo-
randomness. Recently she has been captivated by questions related to understanding the
power and limitations of algebraic computation, as well as to understanding the potential
of locality in algorithms for codes.
Shubhangi discovered her love for mathematics in her high school years at the Bhaskara-
charya Pratishthana, an educational and research institute in mathematics in Pune, under
the guidance and mentoring of her teacher Mr. Prakash Mulabagal. Mr. Prakash ran an
amazing program aimed at getting high school students from across Pune introduced
to the joy of math and the sciences beyond what any school curriculum in Pune could
possibly attempt to do. Shubhangi owes a great deal of her enthusiasm for math problem
solving to Mr. Prakash, and also to being able, through the Bhaskaracharya Pratishthana
program, to make close friends in Pune who were into the same thing.
Thanks to this nurturing environment, Shubhangi got involved in math competitions
and represented India twice at the International Mathematical Olympiad (IMO), once
winning a bronze medal (2002) and once a silver (2003).
She went on to do her undergraduate studies in Mathematics at MIT, graduating in 2007.
She did not really know that she wanted to stay on in academia until her junior year
when she spent a year abroad as a mathmo at Cambridge University in the UK where she
took fantastic courses by Tim Gowers and Imre Leader. Once back at MIT, in summer
2006, she did a research project with Igor Pak at MIT, which gave her a lot of confidence
and encouragement. She was also fortunate to take some more great courses at MIT;
“Randomized algorithms” by David Karger and “Complexity theory” by Madhu Sudan
were particularly influential. The support and encouragement from her MIT mentors
eventually got her on the path to theoretical computer science.
In her spare time Shubhangi enjoys reading, cooking, long walks, and exploring cafés
and restaurants. Her little toddler is a constant source of joy and amazement, and she
also makes sure there isn’t much time to spare.
T HEORY OF C OMPUTING, Volume 13 (6), 2017, pp. 1–33 33