Plaintext
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177
www.theoryofcomputing.org
Elusive Functions and Lower Bounds for
Arithmetic Circuits
Ran Raz∗
Received: June 3, 2008; revised: May 15, 2010; published: September 11, 2010.
Abstract: It is a basic fact of linear algebra that the image of the curve
f (x) = (x1 , x2 , x3 , . . . , xm ) ,
say over C, is not contained in any (m − 1)-dimensional affine subspace of Cm . In other
words, the image of f is not contained in the image of any polynomial mapping Γ : Cm−1 →
Cm of degree 1 (that is, an affine mapping). Can one give an explicit example of a poly-
nomial curve f : C → Cm such that the image of f is not contained in the image of any
polynomial mapping Γ : Cm−1 → Cm of degree 2?
In this paper, we show that problems of this type are closely related to proving lower
bounds for the size of general arithmetic circuits. For example, any explicit f as above
o(1)
(with the right notion of explicitness), of degree up to 2m , implies super-polynomial
lower bounds for computing the permanent over C.
More generally, we say that a polynomial mapping f : Fn → Fm is (s, r)-elusive, if for
every polynomial mapping Γ : Fs → Fm of degree r, Image( f ) 6⊂ Image(Γ). We show that
for many settings of the parameters n, m, s, r, explicit constructions of elusive polynomial
mappings imply strong (up to exponential) lower bounds for general arithmetic circuits.
∗ Research supported by the Israel Science Foundation (ISF), the Binational Science Foundation (BSF) and the Minerva
Foundation.
ACM Classification: F.2.2, F.1.3, F.1.2, G.2.0
AMS Classification: 68Q15, 68Q17, 94C05
Key words and phrases: complexity theory, lower bounds, separation of complexity classes, circuit
complexity, arithmetic circuits, polynomials
2010 Ran Raz
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2010.v006a007
R AN R AZ
Finally, for every r < log n, we give an explicit example of a polynomial mapping f :
2
Fn → Fn , of degree O(r), that is (s, r)-elusive for s = n1+Ω(1/r) . We use this to construct for
any r, an explicit example of an n-variate polynomial of total-degree O(r), with coefficients
in {0, 1}, such that any depth-r arithmetic circuit for this polynomial (over any field) is of
size ≥ n1+Ω(1/r) .
In particular, for any constant r, this gives a constant degree polynomial such that any
depth-r arithmetic circuit for this polynomial is of size ≥ n1+Ω(1) . Previously, only lower
bounds of the type Ω(n · λr (n)), where the λr are extremely slowly growing functions, were
known for constant-depth arithmetic circuits for polynomials of constant degree (actually,
for linear functions).
1 Introduction
We present a family of problems that are very simple to describe, that seem natural to study from several
different points of view (such as, geometric, algebraic and combinatorial), that are seemingly unrelated
to arithmetic circuit complexity, and whose solution would give strong (up to exponential) lower bounds
for the size of general arithmetic circuits. We then prove lower bounds of n1+Ω(1/d) for the size of
arithmetic circuits of depth d for explicit polynomials of degree O(d).
Let F be a field. A polynomial mapping f : Fn → Fm of degree r is a function such that each of its
coordinates can be presented as a polynomial of total-degree at most r in the input variables. We say
that a polynomial mapping f : Fn → Fm is (s, r)-elusive, if for every polynomial mapping Γ : Fs → Fm of
degree r, Image( f ) 6⊂ Image(Γ). (For more details about polynomial mappings and elusive polynomial
mappings, see Subsection 1.4.) Can one give explicit examples of elusive polynomial mappings?
We show that for many settings of the parameters, explicit constructions of elusive polynomial map-
pings imply strong (up to exponential) lower bounds for general arithmetic circuits. (Here, and below,
explicit means poly(n)-definable, as defined in Definition 1.3. In particular, f : Fn → Fm is poly(n)-
definable if given a monomial q and an index i, the coefficient of the monomial q in the polynomial fi
can be computed in time poly(n). For more details, see Subsection 1.5.) For example, we show the
following results: Let F be a field of characteristic not equal to 2.
1. Let s = s(n), m = m(n) be such that nω(1) ≤ m (i. e., m is super-polynomial in n) and s ≥ m0.9 .
(Think of m as relatively small, say m = nlog log n .)
If there exists an explicit (s, 2)-elusive polynomial mapping, f : Fn → Fm (of degree at most
poly(n)), then any arithmetic circuit for the permanent, over F, is of super-polynomial size.
2. Let s = s(n), m = m(n), r = r(n) be such that nω(1) ≤ s < m = nr . (Think of r as relatively small,
say r = log log n, and hence m = nlog log n ; and think of s as significantly smaller than m, say
s = nlog log log n .)
If there exists an explicit (s, r)-elusive polynomial mapping, f : Fn → Fm (of degree at most
poly(n)), then any arithmetic circuit for the permanent, over F, is of super-polynomial size.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 136
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
In other words, one can prove super-polynomial lower bounds for the permanent, simply by con-
structing elusive polynomial mappings.
We note that in the above two examples (as well as in all other cases discussed in this paper),
an elusive polynomial mapping f : Fn → Fm of degree up to 2n , (rather than poly(n)), is also sufficient,
2
since we can easily construct from it a multilinear polynomial mapping fˆ : Fn → Fm such that the image
of f is contained in the image of fˆ. We prefer to state our results with the seemingly weaker upper bound
of poly(n) on the degree, because there is no standard notion for explicitness of polynomials of degree
larger than poly(n), while there is a standard and well established notion for explicitness of polynomials
of degree up to poly(n). For more details, see Subsections 1.4 and 1.5.
In both of the above two examples, as well as in all other cases discussed in this paper, it is not hard
to show the existence of (non-explicit) polynomial mappings f : Fn → Fm , with the required properties.
The hard problem is to construct f explicitly.
We note also that polynomial mappings f : Fn → Fm , as above, can easily be constructed from a
set H of 2n points in Fm such that for every mapping Γ : Fs → Fm , as above, H is not contained in the
image of Γ. Once again, it is not hard to prove the existence of such a set H, and the hard problem is to
construct H explicitly.
When one is interested in proving polynomial lower bounds (rather than super-polynomial lower
bounds), one can even assume that the mapping Γ is given as an input. For example, we can prove the
following result: Let F be any field. Let s = n90 , and let m = n100 . Let Γ : Fs → Fm be a polynomial
mapping of degree 2, with coefficients in {0, 1}. Note that Γ can be described by poly(n) bits. We show
that if one can give a polynomial-time Turing machine that on input Γ, as above, outputs an explicit
polynomial mapping f : Fn → Fm of degree at most poly(n), such that Image( f ) 6⊂ Image(Γ), then one
obtains an explicit lower bound of Ω(n10 ) for the size of arithmetic circuits.
Note also, that in order to obtain the above mentioned explicit lower bound of Ω(n10 ) for the size
of arithmetic circuits, it is enough to give a polynomial-time Turing machine that on input Γ, as above,
outputs one point outside the image of Γ. Thus, one can also obtain “win-win” results, such as: either
the problem of finding a point outside the image of a polynomial mapping Γ is hard (when Γ is given as
an input), in which case we have an example of a hard problem, or, otherwise, there exists an explicit
lower bound of Ω(n10 ) for the size of arithmetic circuits (or both).
2
Finally, for every r < log n, we give an explicit example of a polynomial mapping f : Fn → Fn , of
degree O(r), that is (s, r)-elusive for s = n1+Ω(1/r) . We use this to prove lower bounds for bounded-depth
arithmetic circuits, for polynomials of bounded degree. For any r = r(n), we give an explicit example
of an n-variate polynomial of degree O(r), with coefficients in {0, 1}, such that any (unbounded fanin)
depth-r arithmetic circuit for this polynomial, over any field, is of size ≥ n1+Ω(1/r) . In particular, for
any constant r, this gives a constant degree polynomial such that any depth-r arithmetic circuit for this
polynomial is of size ≥ n1+Ω(1) . Previously, only slightly super-linear lower bounds were known for
constant-depth arithmetic circuits, for polynomials of constant degree (actually, for linear functions).
1.1 Arithmetic circuits
Let F be a field, and let {x1 , . . . , xn } be a set of input variables. An arithmetic circuit is a directed acyclic
graph, as follows: Every leaf of the graph (i. e., a node of in-degree 0) is labelled with either an input
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 137
R AN R AZ
variable or the field element 1. Every other node of the graph is labelled with either + or × (in the first
case the node is a sum-gate and in the second case a product-gate). Every edge in the graph is labelled
with an arbitrary field element. A node of out-degree 0 is called an output-gate of the circuit.
Every node and every edge in an arithmetic circuit compute a polynomial in the ring F[x1 , . . . , xn ] in
the following way. A leaf just computes the input variable or field element that labels it. An edge (u, v),
labelled by α ∈ F, computes the product of α and the polynomial computed by u. A sum-gate computes
the sum of the polynomials computed by all edges that reach it. A product-gate computes the product
of the polynomials computed by all edges that reach it. We say that a polynomial g ∈ F[x1 , . . . , xn ] is
computed by the circuit if it is computed by one of the circuit’s output-gates.
The size of a circuit Φ is defined to be the number of edges in Φ, and is denoted by Size(Φ). (We
assume w.l.o.g. that the size of a circuit is larger than the number of its input variables and the number
of its output-gates.) The depth of a circuit Φ is defined to be the length of the longest directed path in Φ,
and is denoted by Depth(Φ). If (u, v) is an edge in the circuit, we say that u is a child of v and v is a
parent of u. The fanin of a circuit is defined to be the maximal in-degree of a node in the circuit, that
is, the maximal number of children that a node has. Note that we do not restrict the fanin of a circuit to
be 2.
1.2 Background
Arithmetic circuits is the standard computational model for computing polynomials (e. g., for computing
the determinant or the permanent of a matrix, or the product of two matrices). If one considers polyno-
mials of very high degree, it is not hard to prove high lower bounds for the size and depth of arithmetic
n
circuits. For example, any arithmetic circuit for the polynomial x2 is obviously of depth at least n.
However, interesting polynomials that we would like to study are usually of degree bounded by poly(n)
(where n is the number of input variables). Hence, the discussion is usually restricted to polynomials
of degree at most poly(n), and special attention is given for proving lower bounds for polynomials of a
relatively low degree (e. g., constant degree).
The landmark results of Strassen [35] and Baur and Strassen [5] give lower bounds of Ω(n log r)
for the size of arithmetic circuits for explicit n-variate polynomials of degree r. In particular, when the
degree r is poly(n), this gives explicit lower bounds of Ω(n log n). For polynomials of constant degree,
there are no lower bounds better than Ω(n).
Proving super polynomial lower bounds for arithmetic circuits (for explicit polynomials) is one of
the most challenging open problems in computational complexity. Such lower bounds are only known
for some restricted classes of arithmetic circuits. For example, super polynomial lower bounds were
proved for non-commutative formulas [19], for multilinear formulas [25, 24], and for circuits of depth 3
over finite fields [12, 13].
For additional background on arithmetic circuit complexity, see [11, 7].
1.3 Constant-depth arithmetic circuits
Exponential lower bounds for the size of constant-depth Boolean circuits (for explicit functions) are
well known [9, 2, 38, 14, 29, 33]. In particular, exponential lower bounds for constant-depth Boolean
circuits over the basis {∧, ∨, ¬, ⊕} were given by Razborov [29]. This gives exponential lower bounds
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 138
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
for constant-depth arithmetic circuits over the field GF(2), since a product over GF(2) is just the ∧
operation, and a sum over GF(2) is just the ⊕ operation.
However, for constant-depth arithmetic circuits over other fields, much less is known. In particular,
super-polynomial lower bounds are not known, even for circuits of depth 4. For circuits of depth 3
over finite fields, exponential lower bounds were proved by Grigoriev and Karpinski [12] and Grigoriev
and Razborov [13]. For circuits of depth 3 over infinite fields, only quadratic lower bounds are known,
(proved by Shpilka and Wigderson [32]).
In this paper, we are interested in proving lower bounds for constant-depth arithmetic circuits, for
polynomials of constant degree. Recall that Baur and Strassen proved a lower bound of Ω(n log r) for
the size of arithmetic circuits of any depth, where r is the degree of the polynomial computed. Note,
however, that if one considers polynomials of constant degree, this only gives a linear lower bound.
Super-linear lower bounds for constant-degree polynomials (actually, for linear functions), for arithmetic
circuits of constant-depth, are well known (proved by Pudlak [21] and by [27]). These bounds, however,
are extremely weak. For circuits of depth d, these bounds are of the type Ω(n · λd (n)), where λd (n)
are extremely slowly growing functions (e. g., λ5 (n) = log∗ n, and λ7 (n) = log∗ log∗ n). These bounds
are based on the fact that very small graphs of very small depth cannot be super-concentrators, and
the proofs use complicated combinatorial arguments, first used to prove lower bounds for the size of
super-concentrators [8, 21].
As mentioned above, in this work we give for any d, an explicit example of a polynomial of degree
O(d) such that any depth-d arithmetic circuit for this polynomial is of size ≥ n1+Ω(1/d) . In particular,
for any constant d, this gives a constant degree polynomial such that any depth-d arithmetic circuit for
this polynomial is of size ≥ n1+Ω(1) .
Previous to our work, a very related approach was used by Shoup and Smolensky to show the ex-
istence of points p1 , . . . , pn ∈ C such that any arithmetic circuit of depth d, over C, for polynomial
evaluation (or interpolation) at these points, is of size Ω(dn1+1/d ) [31]. This gives a lower bound of
Ω(dn1+1/d ) for depth-d arithmetic circuits, for non-explicit linear-forms, over C. We note also, that one
can view the points p1 , . . . , pn as a part of the input to the circuit and hence view the lower bound of [31]
as a lower bound for explicit polynomials of degree O(n) (rather than a lower bound for non-explicit
linear-forms).
The techniques used by Shoup and Smolensky are very related to ours. In particular, implicit in
2
their work is an explicit example of a polynomial mapping f : Fn → Fn , of degree O(n), that is (s, r)-
elusive for s = n1+Ω(1/r) ; and that function is used there to prove their lower bound. This compares to
2
an explicit construction of a polynomial mapping f : Fn → Fn , of degree O(r), that is (s, r)-elusive for
s = n1+Ω(1/r) , that we present here (for every r < log n); and that we use here to prove our lower bound.
The construction of the function, and the proof that it is elusive is the main technical difference between
the two proofs.
Thus, our lower bounds for bounded-depth arithmetic circuits can be viewed as a generalization and
improvement of the techniques and results of Shoup and Smolensky. The main technical difference
between the results is that our lower bound is for polynomials of degree O(d) while their lower bound
(when viewed as a lower bound for explicit polynomials) is for polynomials of degree O(n). There are
several other differences, as follows:
1. In [31], the points p1 , . . . , pn were not viewed as a part of the input to the circuit. Hence, Shoup
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 139
R AN R AZ
and Smolensky do not view their result as a lower bound for explicit polynomials, and rather state
their lower bound as a lower bound for non-explicit linear-forms. Here, we view (the equivalent
of) the points p1 , . . . , pn as a part of the input to the circuit, and hence we obtain lower bounds for
explicit polynomials.
Technically, this is just an observation.
2. Shoup and Smolensky only prove their lower bounds over C, while here we prove lower bounds
over any field F.
Technically, this improvement is not hard. It is obtained by working over a large enough field
extension G ⊃ F.
3. Shoup and Smolensky’s lower bound (when viewed as a lower bound for explicit polynomials)
is for polynomials of degree O(n), while here we prove lower bounds for polynomials of degree
O(d).
This is the main advantage of our lower bounds over the ones of Shoup and Smolensky. Techni-
cally, this is the main difference between the proofs, and the hard part of our argument.
We will now try to explain the importance of proving lower bounds for polynomials of constant
degree (rather than for polynomials of degree, say, O(n)). One reason is that strong enough lower
bounds for constant-depth arithmetic circuits, for polynomials of constant degree, would imply lower
bounds for general arithmetic circuits!
Consider for example the following trivial but striking fact: Any (unbounded-depth) arithmetic cir-
cuit of size s, for a polynomial of a constant degree r, can be translated into an arithmetic circuit of
size O(s2 ) and depth O(r), for the same1 polynomial.2 Thus, surprisingly, a lower bound of Ω(n2+ε ) for
constant-depth arithmetic circuits, for an explicit polynomial of constant degree, would imply a lower
bound of Ω(n1+ε/2 ) for the size of general arithmetic circuits.
Or consider the following fact: Any fanin-2 arithmetic circuit of depth O(log n) and size O(n1+ε ),
for a polynomial of a constant degree, can be translated into an (unbounded-fanin) arithmetic circuit of
0
size O(n1+ε ) and constant-depth, for the same polynomial, (for any ε 0 > ε).3 Thus, a lower bound of
0
Ω(n1+ε ) for constant-depth arithmetic circuits, for polynomials of constant degree, would imply a lower
bound of Ω(n1+ε ) for fanin-2 arithmetic circuits of depth O(log n), that is, a strong size-depth tradeoff
for general arithmetic circuits.
Thus, our lower bounds are close to the best possible, without implying strong size-depth tradeoffs
for general arithmetic circuits.
1 This is done roughly as follows: we will have r levels in the new circuit, where the nodes in level i compute the parts
of degree i of all polynomials computed by nodes in the original circuit (by a depth-2 circuit that uses nodes from previous
levels).
2 Moreover, any arithmetic circuit of size s, for a polynomial of degree r, can be translated into an arithmetic circuit of
size poly(s, r) and depth O(log r), for the same polynomial [37].
3 One can start from any fanin-2 arithmetic circuit of depth d = O(log n) and size s (for a polynomial of a constant degree,
say, 10), and translate it into an unbounded-fanin arithmetic circuit of depth d/(δ log n) = O(1) and size s · nO(δ ) (for any
constant δ > 0). This is done roughly as follows: first, assume without loss of generality that every partial computation in the
circuit computes a polynomial of constant degree. Then, replace any partial computation of depth δ log n by a straightforward
computation of the polynomial that it computes.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 140
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
Finally, we note that our lower bounds match size-depth tradeoffs (of n1+Ω(1/d) ) that were previ-
ously known for, so called, bounded coefficient circuits, a restricted class of arithmetic circuits over the
field C [20, 17, 22, 23].
1.4 Polynomial mappings
Let F be a field. A polynomial mapping f : Fn → Fm of degree r is a tuple f = ( f1 , . . . , fm ), where for
every i ∈ {1, . . . , m}, fi (x1 , . . . , xn ) ∈ F[x1 , . . . , xn ] is a polynomial of total-degree at most r.4 The mapping
f is multilinear, if f1 , . . . , fm are multilinear polynomials (i. e., the degree of every input variable in every
fi is at most 1). The mapping f is homogenous, if f1 , . . . , fm are homogenous polynomials of the same
total-degree (i. e., the total-degree of every monomial in every fi is the same). We denote the image of a
polynomial mapping f by Image( f ).
Note that given polynomials f1 , . . . , fm ∈ F[x1 , . . . , xn ], for any field extension G ⊃ F, we can think
of f = ( f1 , . . . , fm ) as a polynomial mapping f : Gn → Gm (since F[x1 , . . . , xn ] ⊂ G[x1 , . . . , xn ]).
Definition 1.1 (Eludes, Elusive). We say that a polynomial mapping f : Fn → Fm eludes a polynomial
mapping Γ : Fs → Fm if Image( f ) 6⊂ Image(Γ). We say that f : Fn → Fm is (s, r)-elusive, if it eludes
every polynomial mapping Γ : Fs → Fm of degree at most r.
For every r and every polynomial mapping f : Fn → Fm of degree less than 2r in each variable, we
can construct a multilinear polynomial mapping fˆ : Fn·r → Fm such that the image of f is contained in
the image of fˆ. This is done as follows. For every input variable xi , we introduce r new input variables
xi,1 , . . . , xi,r . We replace every occurrence of xik (in each of the polynomials f1 , . . . , fm ) by the product
kj
∏rj=1 xi, j , where (kr , . . . , k1 ) is the binary representation of k.
Proposition 1.2. Let f : Fn → Fm be a polynomial mapping of degree less than 2r in each variable, and
let fˆ : Fn·r → Fm be the multilinear polynomial mapping as above. Then Image( f ) ⊂ Image( fˆ).
Proof. For any a1 , . . . , an ∈ F,
r−1 r−1
f (a1 , . . . , an ) = fˆ(a11 , a21 , . . . , a12 , · · · , a1n , a2n , . . . , an2 ).
By Proposition 1.2, if f eludes a mapping Γ, then so does fˆ. In particular, if f is (s, r)-elusive,
then so is fˆ. For that reason, it is enough for us to limit the discussion to polynomial mappings f that
are multilinear, and in particular, are of degree at most poly(n). (Note, however, that the polynomial
mappings Γ that we consider are not necessarily multilinear.)
4 Note that given a function f : Fn → Fm , the representation of f , . . . , f as polynomials in F[x , . . . , x ], if exists, is not
1 m 1 n
necessarily unique (if F is finite). Hence, we assume that a polynomial mapping f : Fn → Fm , is already given as a tuple
( f1 , . . . , fm ) of polynomials in F[x1 , . . . , xn ].
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 141
R AN R AZ
1.5 Explicit polynomial mappings
The standard notion of explicitness of a polynomial f ∈ F[x1 , . . . , xn ] is that f is explicit if it is (uniformly)
poly(n)-definable, that is, it belongs to the (uniform version of the) class VNP, Valiant’s algebraic ver-
sion of the class NP [36] (see also [10, 6]).
Formally, f ∈ F[x1 , . . . , xn ] is poly(n)-definable, iff for some ` = poly(n), there exists a polyno-
mial g ∈ F[x1 , . . . , xn , e1 , . . . , e` ] of degree poly(n), that can be computed by an arithmetic circuit of size
poly(n), and such that
f (x1 , . . . , xn ) = ∑ g(x1 , . . . , xn , e1 , . . . , e` )
e1 ,...,e` ∈{0,1}
(see [6], Definition 2.5, or [10], Theorem 4.2). Many equivalent definitions of poly(n)-definability can
be found in [10, 6].
In particular, if f is multilinear with coefficients in {0, 1}, and there exists a deterministic polynomial-
time Turing machine that on inputs e1 , . . . , en ∈ {0, 1} outputs the coefficient of the monomial x1e1 · · · xnen
in f , then f is poly(n)-definable (see [10], Proposition 4.4)
Here, we extend the notion of poly(n)-definability to polynomial mappings f : Fn → Fm , by the
following definition.
Definition 1.3 (poly(n)-Definable). A polynomial mapping f : Fn → Fm is poly(n)-definable if for some
.
` = poly(n), and for k = dlog2 me, there exists a polynomial g ∈ F[x1 , . . . , xn , e1 , . . . , e` , w1 , . . . , wk ] of
degree poly(n), that can be computed by an arithmetic circuit of size poly(n), and such that for every
i ∈ {1, . . . , m},
fi (x1 , . . . , xn ) = ∑ g(x1 , . . . , xn , e1 , . . . , e` , i1 , . . . , ik ) ,
e1 ,...,e` ∈{0,1}
(where (ik , . . . , i1 ) is the binary representation of i − 1).
Note that we allow the size of the arithmetic circuit for g to depend polynomially on n, but we do
not allow it to depend polynomially on m. This is important because we will consider cases where m is
super-polynomial in n. Intuitively, this means that it is not enough that for every i the function fi can be
defined by a different polynomial-size arithmetic circuit gi . We require that f1 , . . . , fm can all be defined
by the same polynomial-size arithmetic circuit g.
Finally, we note that if f : Fn → Fm is a multilinear polynomial mapping, and the coefficient of every
monomial in every fi is in {0, 1}, and there exists a deterministic polynomial-time Turing machine that
on inputs i and e1 , . . . , en ∈ {0, 1} outputs the coefficient of the monomial x1e1 · · · xnen in fi , then, the
polynomial mapping f is poly(n)-definable.
1.6 Techniques
Denote by m = n+r−1
r the number of monomials of total-degree r in n variables. Consider polynomials
g ∈ F[z1 , . . . , zn ] of total-degree r. Every such polynomial g can be viewed as a vector of m coefficients,
that is, a vector in Fm .
We take a universal arithmetic circuit, with s edges, and consider the polynomial g ∈ Fm computed
by the circuit, as a function of the s labels of the edges of the circuit. This defines a polynomial mapping
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 142
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
Γ : Fs → Fm . We show that if one takes an arithmetic circuit in the right form, the mapping Γ is of a
relatively small degree.
Roughly speaking, we can show, for example, that for every n, r, s0 , there is s = poly(s0 , n, r), and a
polynomial mapping Γ : Fs → Fm , of degree O(r), such that if g is computable by an arithmetic circuit
of size s0 , then g is in the image of Γ, (and if g is in the image of Γ then g is computable by an arithmetic
circuit of size s). Moreover, the mapping Γ can be efficiently constructed in time poly(sr ).
Thus, the image of the polynomial mapping Γ captures the set of polynomials of low complexity. A
polynomial is of low complexity only if it is in the image of Γ. Thus, our goal in proving lower bounds
is just to find polynomials that are not in the image of Γ.
There are several possible ways to approach this problem. First, one can try to take the explicit de-
scription of Γ and find (say, in polynomial time) a point outside its image. Since the explicit description
of Γ is of size poly(sr ), this approach is limited to s, r such that sr = poly(n), and hence is limited to
proving polynomial lower bounds. Note, however, that one can also try to use this approach for finding
polynomials of super-polynomial complexity, in super-polynomial time.
A more promising approach (at least if one is interested in proving unconditional super-polynomial
lower bounds), is to try to find a set of points that is not contained in the image of Γ, for any polynomial
mapping Γ : Fs → Fm of degree O(r).
Consider for example a polynomial f ∈ F[x1 , . . . , xn , z1 , . . . , zn ], of total-degree r in the set of variables
{z1 , . . . , zn }. For every a1 , . . . , an ∈ F, we can substitute x1 = a1 , . . . , xn = an and obtain a polynomial
fa1 ,...,an ∈ F[z1 , . . . , zn ] of total-degree r, that is, a point in Fm . Thus, we obtain a polynomial mapping
f 0 : Fn → Fm . If Image( f 0 ) 6⊂ Image(Γ) then one of the polynomials fa1 ,...,an cannot be computed by a
circuit of size s0 , and hence f cannot be computed by a circuit of size s0 . If, in addition, f is explicit, we
obtain an explicit lower bound for arithmetic circuits.
How to prove that Image( f 0 ) 6⊂ Image(Γ)? One idea that comes to mind is to prove the existence of
a polynomial Λ : Fm → F, such that, Λ ◦ Γ ≡ 0, while Λ ◦ f 0 6≡ 0. We use this idea to obtain our lower
bounds for bounded-depth arithmetic circuits in Section 4.
We note that many variants of these ideas can also be considered. For example, if the model of
computation is restricted, one can capture the polynomials of low complexity by a mapping Γ that may
have some additional helpful properties. Another idea that comes to mind is to try to prove the existence
of a polynomial g ∈ Fm such that there is a short proof for the statement g 6∈ Image(Γ).
Finally we note that in several places in this work we will use the result of Baur and Strassen
that if a polynomial can be computed by an arithmetic circuit of size s and depth d, then all partial
derivatives of that polynomial can be computed by one arithmetic circuit of size 5s and depth 3d [5] (for
an improvement of the constants see [18]). For that reason, we will consider in Section 3 and Section 4
a tuple of polynomials, rather than a single polynomial g. This will improve the parameters in some of
our results, by applying the result of Baur and Strassen. In Section 5, we work with a single polynomial
g (which is somewhat simpler).
1.7 Related work
The idea to consider a polynomial computed by a circuit, as a function of the labels of the edges of
the circuit, goes back to the works of Strassen [34] and Lipton [16], in the context of arithmetic cir-
cuits with a single input variable. Strassen and Lipton used this idea to prove non-explicit lower bounds
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 143
R AN R AZ
for arithmetic circuits with a single input variable. Years after, the same idea was used by Shoup and
Smolensky [31], in the context of bounded-depth linear arithmetic circuits (i. e., bounded-depth arith-
metic circuits without product-gates). To the best of our knowledge, previous to our work, the idea was
not used for general arithmetic circuits. As mentioned above, the work of Shoup and Smolensky [31]
is very related to ours also in the way in which we prove lower bounds for bounded-depth arithmetic
circuits. Moreover, an explicit example of an elusive function (with certain parameters) is implicit in
their work, and is used there to prove their lower bound. (For more details, see the detailed discussion in
Subsection 1.3.) As far as we know, [31] is the first and only previous work that uses elusive functions
to prove lower bounds. Our results suggest that these ideas can possibly be extended to the more general
setting of general arithmetic circuits.
Another related paper is the work of Impagliazzo and Kabanets [15]. Impagliazzo and Kabanets
proved that if one can test in deterministic polynomial time (or even in nondeterministic subexponen-
tial time), whether a given arithmetic circuit over the integers computes the identically-zero polynomial,
then, either NEXP 6⊂ P/poly, or the permanent is not computable by polynomial-size arithmetic circuits.
This result is related to ours, since constructing an elusive function can also be viewed as a derandom-
ization problem.
Another idea, related to ours, in the area of propositional proof complexity, was to study the length
of propositional proofs for tautologies of the form b 6∈ Image(G), for pseudorandom generators G :
{0, 1}n → {0, 1}m [3]. It was proved in [3], (as well as in subsequent works, e. g., [4]), that for some
functions G : {0, 1}n → {0, 1}m , tautologies of this form are hard to prove in several well-studied propo-
sitional proof systems. We refer the reader to [3] for the many motivations (given there) for studying
such tautologies. We note only that one of the original motivations for studying these tautologies was
that one can consider a function G that maps a description of a Boolean circuit to the truth-table of the
function computed by it (see also [30]). For this particular function G, proving that tautologies of the
form b 6∈ Image(G) are hard for a propositional proof system P, can be interpreted as: proving circuit
complexity lower bounds are hard in the proof system P. We find these ideas very related to ours.
Finally we note that in this work we also prove a (folklore) result that strong enough exponential
lower bounds for depth-4 circuits imply exponential lower bounds for general circuits (see Proposi-
tion 2.7). A beautiful recent work of Agrawal and Vinay [1] (using [37]) shows the stronger result
that any exponential lower bound for depth-4 circuits implies exponential lower bounds for general cir-
cuits. A very recent work [26] proves that extremely strong lower bounds for depth-3 formulas imply
super-polynomial lower bounds for general formulas.
1.8 Our results
We partition our results about the connections between polynomial mappings and lower bounds for
arithmetic circuits into two groups: Results for polynomial mappings f that elude polynomial mappings
Γ of degree 2, and results for polynomial mappings f that elude polynomial mappings Γ of degree larger
than 2.
We will first prove our results for polynomial mappings f that elude polynomial mappings Γ of
degree larger than 2. Then, using these results, we will prove our lower bounds for bounded-depth
arithmetic circuits. Finally, we will prove our results for polynomial mappings f that elude polynomial
mappings Γ of degree 2.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 144
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
Recall that given a polynomial mapping f : Fn → Fm , and given a field extension G ⊃ F, we can
think of f as a polynomial mapping f : Gn → Gm . This is because we assume that a polynomial mapping
f : Fn → Fm is given as a tuple ( f1 , . . . , fm ) of polynomials in F[x1 , . . . , xn ] ⊂ G[x1 , . . . , xn ] (see the
discussion in Subsection 1.4).
1.8.1 Arithmetic circuits and polynomial mappings: Part I
We can now present our main results for polynomial mappings f that elude polynomial mappings Γ
of degree larger than 2. The results are given by five propositions and corollaries. The full results are
restated and proved in Subsection 3.4. For more details, see Section 3.
Let F be a field, and let n be an integer. By r, s, s0 , m, we denote integers, and we think of all these
parameters as functions of the basic parameter n.
Proposition 1.4. For all integers 2 ≤ r ≤ n ≤ s0 , and m = n · n+r−1
r , there exists a polynomial mapping
s m 0 2 8
(described in Proposition 3.3), Γ : F → F , (where s = O((s ) · r )), of degree 2r − 1, such that the
following holds: Let f : Fn → Fm be a polynomial mapping. If over some field extension G ⊇ F,
Image( f : Gn → Gm ) 6⊂ Image(Γ : Gs → Gm ) ,
then any arithmetic circuit (over F) for a polynomial f˜ : F3n → F (explicitly defined from f in Subsec-
tion 3.3), is of size > s0 /5.
Moreover, one can construct Γ in time poly(sr ) in the following sense. There exists a poly(sr )-time
Turing machine, that on input n, r, s0 , outputs (all the coefficients of) the m polynomials
(ΓG )1 , . . . , (ΓG )m ∈ F[y1 , . . . , ys ] ,
and such that all the coefficients in these polynomials are integers5 in {0, . . . , (3r)!}.
Corollary 1.5. Let 2 ≤ r ≤ n ≤ s, and m = n · n+r−1
r be integers. Let f : Fn → Fm be a polynomial
mapping. If over some field extension G ⊇ F, f is (s, (2r − 1))-elusive (see Definition 1.1), then any
arithmetic circuit (over F) for a polynomial f˜ : F3n → F (explicitly defined from f in Subsection 3.3), is
√
of size ≥ Ω( s/r4 ).
Corollary 1.6. Let F be a field of characteristic not equal to 2. Let 2 ≤ r ≤ n ≤ s, and m = n · n+r−1
r
be integers such that s = nω(1) . If there exists a poly(n)-definable polynomial mapping f : Fn → Fm such
that, over some field extension G ⊇ F, f is (s, (2r − 1))-elusive (see Definition 1.3 and Definition 1.1),
then any arithmetic circuit for the permanent over F is of size ≥ sΩ(1) .
Corollary 1.7. Let 2 ≤ r ≤ n ≤ s, and m = n · n+r−1
r be integers (and recall that we think of r, s, m as
functions of n). Assume that there exists a poly(sr )-time Turing machine T such that:
• The inputs for T are r, n, s, m and a polynomial mapping Γ : Fs → Fm of degree 2r − 1, given by all
coefficients of the polynomials Γ1 , . . . , Γm (that are assumed to be integers in, say, {0, . . . , (3r)!}).
5 We think of the integers as members of every field, by the inductive definition n = (n − 1) + 1.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 145
R AN R AZ
• The output of T is a poly(n)-definable polynomial mapping f : Fn → Fm (described, e. g., by an
arithmetic circuit for the polynomial g that defines it in Definition 1.3) such that, over some field
extension G ⊇ F,
Image( f : Gn → Gm ) 6⊂ Image(Γ : Gs → Gm ) .
Then, there exists a poly(sr )-time Turing machine that on input n outputs a 3n-variables, poly(n)-
definable, polynomial f˜ (explicitly defined from f in Subsection 3.3, and described, e. g., by an arithmetic
circuit for the polynomial g that defines it in Definition 1.3), such that any arithmetic circuit for f˜ is of
√
size ≥ Ω( s/r4 ).
Proposition 1.8 gives the connection for arithmetic circuits of depth d, and is the one used to prove
our lower bounds for bounded-depth arithmetic circuits.
Proposition 1.8. Let n, d ≤ s, and m = n2 be integers. Let f : Fn → Fm be a polynomial mapping. If over
some field extension G ⊇ F, f is (s, d)-elusive (see Definition 1.1), then any depth-d arithmetic circuit
(over F) for the n polynomials f˜1 , . . . , f˜n : F2n → F (explicitly defined from f in Subsection 3.3), is of
size > s. (Moreover, the degree of each f˜i is at most the degree of f plus 1.)
1.8.2 Lower bounds for bounded-depth circuits
We can now state our lower bounds for bounded-depth arithmetic circuits. We give an explicit construc-
tion for an (s, d)-elusive polynomial mapping, with certain parameters s, d. We then use Proposition 1.8
to obtain lower bounds for the size of arithmetic circuits of depth d. The full results are restated and
proved in Section 4.
For an integer k, denote by [k] the set {1, . . . , k}. Let n be a prime. Let m = n2 . Let 1 ≤ d ≤
(log2 n)/100 be an integer. Let d 0 = 5d. Let {xi, j }i∈[d 0 ], j∈[n] be a set of n · d 0 input variables. For every
(a, b) ∈ [n] × [n], define
f(a,b) (x1,1 , . . . , xd 0 ,n ) = ∏ xi,a+i·b
i∈[d 0 ]
(where the sum a + i · b is taken modulo n).
Let f = ( f(1,1) , f(1,2) , . . . , f(n,n) ). Note that for every field G, we can view f as a polynomial mapping
0
f : Gn·d → Gm .
Lemma 1.9. Let n be a prime, and let m = n2 . Let d be an integer such that 1 ≤ d ≤ (log2 n)/100. Let
d 0 = 5d. Let G be a field of size larger than m (e. g., an infinite field). Then, the polynomial mapping
0
f : Gn·d → Gm (as defined above) is (s, d)-elusive (see Definition 1.1), where s = bn1+1/(2d) c.
Let {z1 , . . . , zn }, {w1 , . . . , wn }, be two sets of input variables. Define, for every a ∈ [n],
f˜a = ∑ zb · f(a,b) .
b∈[n]
Define
f˜ = ∑ wa · f˜a .
a∈[n]
Note that every f˜a is a polynomial in n · (d 0 + 1) variables, and is of total-degree d 0 + 1, and f˜ is a
polynomial in n · (d 0 + 2) variables, and is of total-degree d 0 + 2.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 146
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
Corollary 1.10. Let n be a prime, and let 1 ≤ d ≤ (log2 n)/100 be an integer. Any depth-d arithmetic
circuit, over any field F, for the n polynomials (of total-degree 5d + 1 each) f˜1 , . . . , f˜n : Fn·(5d+1) → F,
(as defined above), is of size ≥ n1+1/(2d) .
Corollary 1.11. Let n be a prime, and let 1 ≤ d ≤ (log2 n)/100 be an integer. Any depth-bd/3c arith-
metic circuit, over any field F, for the polynomial (of total-degree 5d + 2) f˜ : Fn·(5d+2) → F, (as defined
above), is of size ≥ n1+1/(2d) /5.
1.8.3 Arithmetic circuits and polynomial mappings: Part II
We will now present our main results for polynomial mappings f that elude polynomial mappings Γ of
degree 2. The results are given by four propositions and corollaries. The full results are restated and
proved in Subsection 5.4. For more details, see Section 5.
Let F be a field, and let n be an integer. By r, s, s0 , m, we denote integers, and we think of all these
parameters as functions of the basic parameter n.
Proposition 1.12. For all integers 3 ≤ r ≤ n ≤ s0 , and m = n+r−1 , and r0 = b2r/3c, there exists a
r
0
polynomial mapping (described in Proposition 5.3), Γ : Fs → Fm (where s = O(s0 · n+rr0 −1 · r3 )), of
degree 2, such that the following holds: Let f : Fn → Fm be a polynomial mapping. If over some field
extension G ⊇ F,
Image( f : Gn → Gm ) 6⊂ Image(Γ : Gs → Gm ) ,
then any arithmetic circuit (over F) for the polynomial f˜ : F2n → F (explicitly defined from f in Subsec-
tion 5.3), is of size > s0 .
Moreover, one can construct Γ in time poly(s, m) in the following sense. There exists a poly(s, m)-
time Turing machine, that on input n, r, s0 , outputs (all the coefficients of) the m polynomials
(ΓG )1 , . . . , (ΓG )m ∈ F[y1 , . . . , ys ] ,
and such that all the coefficients in these polynomials are in {0, 1}.
Corollary 1.13. Let 3 ≤ r ≤ n ≤ s, and m = n+r−1 be integers. Let r0 = b2r/3c. Let f : Fn → Fm be a
r
polynomial mapping. If over some field extension G ⊇ F, f is (s, 2)-elusive (see Definition 1.1), then any
arithmetic circuit (over F) for the polynomial f˜ : F2n → F (explicitly defined from f in Subsection 5.3),
is of size ≥ !
s
Ω n+r0 −1 .
· r 3
r 0
Corollary 1.14. Let F be a field of characteristic not equal to 2. Let 3 ≤ r ≤ n ≤ s, and m = n+r−1
r be
0 n+r0 −1
integers. Let r = b2r/3c. Assume that s/ r0 ≥n ω(1) . If there exists a poly(n)-definable polynomial
n m
mapping f : F → F such that, over some field extension G ⊇ F, f is (s, 2)-elusive (see Definition 1.3
and Definition 1.1), then any arithmetic circuit for the permanent over F is of size ≥
!Ω(1)
s
n+r0 −1
.
r0 · r3
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 147
R AN R AZ
Corollary 1.15. Let 3 ≤ r ≤ n ≤ s, and m = n+r−1
r be integers (and recall that we think of r, s, m as
functions of n). Let r0 = b2r/3c. Assume that there exists a poly(s, m)-time Turing machine T such that:
• The inputs for T are r, n, s, m and a polynomial mapping Γ : Fs → Fm of degree 2, given by all
coefficients of the polynomials Γ1 , . . . , Γm (that are assumed to be in {0, 1}).
• The output of T is a poly(n)-definable polynomial mapping f : Fn → Fm (described, e. g., by an
arithmetic circuit for the polynomial g that defines it in Definition 1.3) such that, over some field
extension G ⊇ F,
Image( f : Gn → Gm ) 6⊂ Image(Γ : Gs → Gm ) .
Then, there exists a poly(s, m)-time Turing machine that on input n outputs a 2n-variables, poly(n)-
definable, polynomial f˜ (explicitly defined from f in Subsection 5.3, and described, e. g., by an arithmetic
circuit for the polynomial g that defines it in Definition 1.3), such that any arithmetic circuit for f˜ is of
size ≥ !
s
Ω n+r0 −1 .
r0 · r3
2 Arithmetic circuits in normal forms
Definition 2.1 (Circuit-Graph). Let Φ be an arithmetic circuit. We denote by GΦ the underlying graph
of Φ, together with the labels of all nodes. That is, the entire circuit, except for the labels of the edges.
We call GΦ , the circuit-graph of Φ.
We use for a circuit-graph G the same terminology as we use for circuits. For example, the size of G
is the number of edges in G, and is denoted by Size(G), and the depth of G is the length of the longest
directed path in G, and is denoted by Depth(G).
Note that different arithmetic circuits, over different fields, can have the same circuit-graph.
For a circuit-graph G, we define the syntactic-degree of a node in G, inductively, as follows. The
syntactic-degree of a leaf is 0 if the leaf is labelled by the field element 1, and 1 if the leaf is labelled
by an input variable. The syntactic-degree of a sum-gate is the maximum of the syntactic-degrees of its
children. The syntactic-degree of a product-gate is the sum of the syntactic-degrees of its children.
For an arithmetic circuit Φ and a node v in Φ, we define the syntactic-degree of v to be its syntactic-
degree in the circuit-graph GΦ . The degree of a circuit is the maximal syntactic-degree of a node in the
circuit.
2.1 Homogenization
A polynomial g is called homogenous, if all the monomials that occur in g (with coefficients not equal
to 0) have the same total-degree.
We say that a circuit-graph G is homogenous if for every sum-gate v in G, the syntactic-degree of
every child of v is the same. We say that G is homogenous of degree r if it is homogenous, and all
output-gates in G are of syntactic-degree exactly r. We say that an arithmetic circuit Φ is homogenous
if the circuit-graph GΦ is homogenous.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 148
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
Note that a circuit-graph G is homogenous iff for every arithmetic circuit Φ (over any field) such
that G = GΦ , and every gate v in Φ, the polynomial computed by the gate v is homogenous.
Definition 2.2 (Normal-Homogenous-Form). Let G be a homogenous circuit-graph. We say that G is in
normal-homogenous-form if it satisfies:
1. All leaves are labelled by input variables (i. e., no leaf is labelled by 1).
2. All edges from the leaves are to sum-gates.
3. All output-gates are sum-gates.
4. The gates of G are alternating. That is, if v is a product-gate and (u, v) is an edge then u is a
sum-gate, and if v is a sum-gate and (u, v) is an edge then u is either a leaf or a product-gate.
5. The in-degree of every product-gate is exactly 2.
6. The out-degree of every sum-gate is at most 1.
We say that an arithmetic circuit Φ is in normal-homogenous-form if the circuit-graph GΦ is in normal-
homogenous-form.
Proposition 2.3. Let F be a field. Let Φ be an arithmetic circuit of size s, for n homogenous polynomials
g1 , . . . , gn ∈ F[x1 , . . . , xn ] of total-degree r ≥ 1 each. Then, there exists an arithmetic circuit Ψ, for the
polynomials g1 , . . . , gn , such that Ψ is in normal-homogenous-form, and the number of nodes in Ψ is
O(s · r2 ). Moreover, given Φ (as an input), Ψ can be efficiently constructed.
Proof. Note that the number of nodes in Φ is O(s). We assume without loss of generality that n < s. We
will describe an algorithm that changes Φ into the required Ψ. For simplicity, we describe all steps of
the algorithm without dealing with the labels of the edges. It is straightforward to verify that in all steps
the labels of the edges can be fixed so that the functionality of the circuit is preserved.
We can assume without loss of generality that no (sum or product) gate in Φ is of in-degree 1 (other-
wise, we just remove such a gate and connect its only child directly to all its parents). For convenience,
we make sure that the in-degree of every (sum or product) gate is exactly 2. This is done by replacing
any product-gate of in-degree larger than 2 by a tree of product-gates of in-degree 2, and any sum-gate
of in-degree larger than 2 by a tree of sum-gates of in-degree 2. This increases the number of nodes in
the circuit by at most s.
Next, we homogenize the circuit. For a polynomial g ∈ F[x1 , . . . , xn ] and an integer i, we define
the homogenous part of degree i of g to be the restriction of g to the set of monomials of total-degree
exactly i. For every node v and every i ∈ {0, . . . , r}, we “split” the node v into r + 1 nodes v0 , . . . , vr ,
where the node vi computes the homogenous part of degree i of the polynomial computed by the node
v. (Note that we just ignore monomials of degree larger than r everywhere in the circuit, as they do
not contribute to the functionality of the circuit). Formally, this is done inductively on the circuit. For
every node v with children u, w, we add a (homogenous) arithmetic circuit with at most O(r2 ) nodes, that
computes v0 , . . . , vr from u0 , . . . , ur and w0 , . . . , wr . We make sure that the in-degree of every product-
gate is still exactly 2. More precisely, if v is a sum-gate, for every i ∈ {0, . . . , r} the circuit that we add
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 149
R AN R AZ
computes vi = ui + wi , and if v is a product-gate, for every i ∈ {0, . . . , r} the circuit that we add computes
vi = ∑ij=0 u j × wi− j .
Altogether, by the end of this step, we obtained a homogenous arithmetic circuit, with product-gates
of in-degree exactly 2, with at most O(s · r2 ) nodes.
Next, we remove every node of syntactic-degree 0. This is done as follows. Let u be a node of
syntactic-degree 0. If u is of out-degree 0, we can just remove it as it cannot contribute to the function-
ality of the circuit. Otherwise, there is an edge (u, v). If v is a sum-gate then, since the circuit is now
homogenous, v is of syntactic-degree 0. Thus v just computes a field element α. So we can just replace
v by a leaf labelled by 1 and multiply the labels of all the edges from v by α. If v is a product-gate, with
other child w, we can remove the gate v and connect w directly to all parents of v. By repeating this
process as many times as needed, we remove all nodes of syntactic-degree 0, and in particular, all leaves
labelled by 1.
Altogether, by the end of this step, we obtained a homogenous arithmetic circuit, with product-gates
of in-degree exactly 2, with no leaves labelled by 1, and with at most O(s · r2 ) nodes.
Next, we ensure that the gates are alternating. This is done as follows. For any edge (u, v) such that
u, v are both product-gates, we add a dummy sum-gate in between them. Note that since the in-degree of
every product-gate is 2, this at most triples the number of nodes in the circuit. For any edge (u, v) such
that u, v are both sum-gates, we connect all children of u directly to v and remove the edge (u, v). This
doesn’t increase the number of nodes. By repeating this as many times as needed, we obtain a circuit
with alternating gates.
Altogether, by the end of this step, we obtained a homogenous arithmetic circuit, with product-gates
of in-degree exactly 2, with no leaves labelled by 1, with alternating gates, and with at most O(s · r2 )
nodes.
Next, we connect any product output-gate to a (different) dummy sum-gate. This at most doubles
the number of nodes in the circuit.
Next, for any edge from a leaf to a product-gate, we add a dummy sum-gate in between them. Note
that since the in-degree of every product-gate is 2, this at most triples the number of nodes in the circuit.
Next, we ensure that the out-degree of every sum-gate is at most 1. This is done by duplicating q
times any sum-gate of out-degree q > 1. Note that since every edge from a sum-gate reaches a product-
gate, and since the in-degree of every product-gate is 2, this at most triples the number of nodes in the
circuit.
Finally, we can remove all nodes of out-degree 0 that do not output one of the polynomials g1 , . . . , gn .
We repeat this as many times as needed.
Altogether, we obtain a circuit in normal-homogenous-form, with at most O(s · r2 ) nodes.
2.2 Linearization
A polynomial g is called linear, if it is homogenous of degree 1, that is, if all the monomials that occur
in g (with coefficients not equal to 0) are of total-degree exactly 1.
Definition 2.4 (Normal-Linear-Form). Let G be a homogenous circuit-graph. We say that G is in
normal-linear-form if it satisfies:
1. All nodes in G are either leaves or sum-gates (i. e., there are no product-gates).
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 150
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
2. All leaves are labelled by input variables (i. e., no leaf is labelled by 1).
Note that this implies that the syntactic-degree of every node v in G is exactly 1. We say that an arithmetic
circuit Φ is in normal-linear-form if the circuit-graph GΦ is in normal-linear-form.
Proposition 2.5. Let F be a field. Let Φ be an arithmetic circuit of size s and depth d, for n linear
polynomials g1 , . . . , gn ∈ F[x1 , . . . , xn ]. Then, there exists an arithmetic circuit Ψ, of size s and depth d,
for the polynomials g1 , . . . , gn , such that Ψ is in normal-linear-form. Moreover, given Φ (as an input),
Ψ can be efficiently constructed.
Proof. We will describe an algorithm that changes Φ into the required Ψ.
For a polynomial g ∈ F[x1 , . . . , xn ], we define the linear part of g to be the restriction of g to the set
of monomials of total-degree exactly 1. For every node v in Φ, we define a node v0 in Ψ that computes
the linear part of the polynomial computed by the node v.
Formally, this is done inductively on the circuit. For a sum-gate v with children v1 , . . . , vk , we define
v0 to be a sum-gate with children v01 , . . . , v0k , and label an edge (v0i , v0 ) with the same field element that
labels (vi , v). For a product-gate v with children v1 , . . . , vk , note that if the linear parts of the polynomials
computed by v1 , . . . , vk are h1 , . . . , hk (respectively), then the linear part of the polynomial computed by
v can be written as ∑ki=1 ci hi , for some field elements c1 , . . . , ck . Thus, once again, we define v0 to be a
sum-gate with children v01 , . . . , v0k , and we label an edge (v0i , v0 ) by ci .
2.3 Reduction to depth 4
We will now define circuit-graphs and arithmetic circuits in a normal-depth-4-form. This form will only
be used in Section 5. Roughly speaking, the computation of an arithmetic circuit in normal-depth-4-form
can be presented as a homogenous sum,6 ∑i Pi Qi , where Pi , Qi are homogenous polynomials of degree
at most 2r/3, where r is the syntactic-degree of the output-gate.
Definition 2.6 (Normal-Depth-4-Form). Let G be a homogenous circuit-graph. We say that G is in
normal-depth-4-form if it satisfies:
1. The out-degree of every gate in G is at most 1 (i. e., G is a tree).
2. There is a single output-gate. The output-gate is a sum-gate.
3. Every directed path from a leaf to the output-gate is of length exactly 4.
4. All edges from the leaves are to product-gates. These product-gates (in the level above the leaves)
are of syntactic-degree at most 2r/3, where r is the syntactic-degree of the output-gate.
5. The gates of G are alternating. That is, if v is a sum-gate and (u, v) is an edge then u is a product-
gate, and if v is a product-gate and (u, v) is an edge then u is either a leaf or a sum-gate.
6. The in-degree of every product-gate, which is a child of the output-gate, is exactly 2.
6 A homogenous sum is a sum of homogenous polynomials, where all the non-zero polynomials in the sum are of the same
degree.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 151
R AN R AZ
We say that an arithmetic circuit Φ is in normal-depth-4-form if the circuit-graph GΦ is in normal-depth-
4-form.
The following proposition is based on a lemma from [28]. (Other forms of it follow from several
previous works.) Note that the proposition implies that strong enough exponential lower bounds for
depth-4 circuits imply exponential lower bounds for general circuits. A recent work of Agrawal and
Vinay [1] (using [37]) shows the stronger result that any exponential lower bound for depth-4 circuits
implies exponential lower bounds for general circuits.
Proposition 2.7. Let F be a field. Let Φ be an arithmetic circuit of size s, for a homogenous polynomial
g ∈ F[x1 , . . . , xn ] of total-degree r ≥ 3. Let r0 = b2r/3c. Then, there exists an arithmetic circuit Ψ, for
0
the polynomial g, such that Ψ is in normal-depth-4-form, and is of size O(s · n+rr0 −1 · r3 ) (and has
0
O(s · n+rr0 −1 · r2 ) product-gates). Moreover, given Φ (as an input), Ψ can be efficiently constructed (in
time polynomial in the size of Ψ).
Proof. We will describe an algorithm that constructs Ψ from Φ.
First, we make sure that the in-degree of every gate in Φ is at most 2. This is done by replacing any
gate of in-degree larger than 2 by a tree of gates of in-degree 2. This increases the number of edges in
the circuit by a factor of at most 2.
Following this, we homogenize the circuit (as in the proof of Proposition 2.3). For a polynomial
h ∈ F[x1 , . . . , xn ] and an integer i, we define the homogenous part of degree i of h to be the restriction of
h to the set of monomials of total-degree exactly i. For every node v and every i ∈ {0, . . . , r}, we “split”
the node v into r + 1 nodes v0 , . . . , vr , where the node vi computes the homogenous part of degree i of
the polynomial computed by the node v. (Note that we just ignore monomials of degree larger than r
everywhere in the circuit, as they do not contribute to the functionality of the circuit.) Formally, this is
done inductively on the circuit. For every node v with children u, w, we add a (homogenous) arithmetic
circuit with at most O(r2 ) edges, that computes v0 , . . . , vr from u0 , . . . , ur and w0 , . . . , wr . We make sure
that the in-degree of every gate is still at most 2. More precisely, if v is a sum-gate, for every i ∈ {0, . . . , r}
the circuit that we add computes vi = ui + wi , and if v is a product-gate, for every i ∈ {0, . . . , r} the circuit
that we add computes vi = ∑ij=0 u j × wi− j .
Altogether, by the end of this step, we obtained a homogenous arithmetic circuit, with gates of in-
degree at most 2, and with at most O(s · r2 ) edges. Denote this circuit by Φ0 , and its size by s0 = O(s · r2 ).
Note that since the circuit is homogenous, and its output-gate computes the polynomial g of degree r, the
syntactic-degree of the output-gate is r. (Formally, we can prove by induction on the nodes of a circuit,
that any node u in a homogenous circuit computes either the 0 polynomial or a homogenous polynomial
of degree exactly equal to the syntactic-degree of u.)
We will now show how to present the polynomial g as a homogenous sum, g = ∑i Pi Qi , where Pi , Qi
are homogenous polynomials of degree at most 2r/3, and the sum is over at most s0 elements. This is
done by induction on s0 .
First note that in the circuit Φ0 there is at least one node u of syntactic-degree larger than r/3 and
smaller or equal to 2r/3. This is true because one can start from the output-gate (which is of syntactic-
degree r) and move in each step from a node v to its child u of larger syntactic-degree. Since the
in-degree of every gate v is at most 2, the syntactic-degree of u is at least a half of the syntactic-degree
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 152
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
of v. Hence, at some point along the way, we reach a node u of syntactic-degree larger than r/3 and
smaller or equal to 2r/3. Let u be such a node.
Denote by P ∈ F[x1 , . . . , xn ] the polynomial computed by the node u of Φ0 . Assume without loss
of generality that P is not the 0 polynomial (otherwise, we can remove the node u and obtain a smaller
circuit, with the same properties, that still computes the polynomial g, and we can continue by induction).
Thus, P is a homogenous polynomial of degree larger than r/3 and smaller or equal to 2r/3.
Let y be an additional input variable. Denote by Φ0u=y , the circuit Φ0 , after replacing the node u by
the input variable y (i. e., we change the label of u to be y and we remove every edge from a child of
u to u). Denote by Φ0u=0 , the circuit Φ0 , after fixing the node u to 0 (i. e., we remove u and all edges
connected to it, and we fix to 0, inductively, all the product-gate parents of u and all the sum-gates that
are left without children).
Note that Φ0u=0 is a homogenous arithmetic circuit (formally, this is proved by induction on the nodes
of the circuit, by showing, inductively, that every node in Φ0u=0 is of the same syntactic-degree as the
corresponding node in Φ0 ), with gates of in-degree at most 2, and with less than s0 edges.
The circuit Φ0u=y computes a polynomial g0 ∈ F[x1 , . . . , xn , y]. Since the syntactic-degree of u in Φ0
is larger than r/3, and since the output of Φ0 is of syntactic-degree r, the degree of y in the polynomial
g0 is at most 2. Hence, we can present g0 as a sum,
g0 = g0 + g1 · y + g2 · y2 ,
where g0 , g1 , g2 ∈ F[x1 , . . . , xn ].
By the definition of Φ0u=0 , the polynomial computed by Φ0u=0 is g0 . Hence, g0 is either the 0 poly-
nomial or a homogenous polynomial of degree r. (Formally, we can show by induction on the nodes of
Φ0u=0 that every node in Φ0u=0 computes either the 0 polynomial or a homogenous polynomial of degree
equals to the syntactic-degree of the corresponding node in Φ0 .)
By the definition of Φ0u=y and by the definition of P, we know that
g = g0 + g1 · P + g2 · P2 = g0 + P · Q ,
where Q = g1 + g2 · P. Note that since both g, g0 are either the 0 polynomial or homogenous polynomials
of degree r, the polynomial P · Q = g − g0 is also either the 0 polynomial or a homogenous polynomial
of degree r. Thus, the sum g = g0 + P · Q is a homogenous sum. Also, since P and P · Q are both
homogenous, Q is also homogenous, and since P · Q is of degree r (unless it is the 0 polynomial), and P
is of degree larger than r/3 and smaller or equal to 2r/3, we conclude that Q is either the 0 polynomial or
is of degree larger or equal to r/3 and smaller than 2r/3. Thus, both P, Q are homogenous polynomials
of degree at most 2r/3.
Since g0 is the polynomial computed by the circuit Φ0u=0 , by induction, g0 can be presented as
a homogenous sum, g0 = ∑i Pi Qi , where Pi , Qi are homogenous polynomials of degree at most 2r/3,
and the sum is over at most s0 − 1 elements. Hence, g can be presented as a homogenous sum, g =
∑i Pi Qi , where Pi , Qi are homogenous polynomials of degree at most 2r/3, and the sum is over at most
s0 elements.
The presentation of g as a homogenous sum, g = ∑i Pi Qi , where Pi , Qi are homogenous polynomials
of degree at most 2r/3, and the sum is over at most s0 elements, gives a homogenous circuit Ψ, for
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 153
R AN R AZ
0
the polynomial g, such that Ψ is in normal-depth-4-form, and is of size O(s · n+rr0 −1 · r3 ) (and has
0
O(s · n+rr0 −1 · r2 ) product-gates). To obtain Ψ, we just have to present every polynomial Pi , Qi , as a sum
of monomials. (Note that since the degree of the polynomials Pi , Qi is at most r0 , their presentations as
0
sums of monomials are by arithmetic circuits of size O( n+rr0 −1 · r0 ), and recall that s0 = O(s · r2 ).)
2.4 Universal circuit-graphs
Proposition 2.8. For any integers n, s, r ≥ 1 such that s ≥ n, there is a circuit-graph G, in normal-
homogenous-form and with at most O(s · r4 ) nodes, that is universal for n-inputs and n-outputs circuits
of size s that compute homogenous polynomials of degree r, in the following sense:
Let F be a field. Let Φ be an arithmetic circuit of size s, for n homogenous polynomials g1 , . . . , gn ∈
F[x1 , . . . , xn ] of total-degree r each. Then, there exists an arithmetic circuit Ψ, for the polynomials
g1 , . . . , gn , such that GΨ = G.
Moreover, given n, s, r, the circuit-graph G can be constructed in time poly(s, r).
Proof. Let F be a field. Let Φ be an arithmetic circuit of size s, for n homogenous polynomials
g1 , . . . , gn ∈ F[x1 , . . . , xn ] of total-degree r. By Proposition 2.3, there exists an arithmetic circuit Ψ0 ,
for the polynomials g1 , . . . , gn , such that Ψ0 is in normal-homogenous-form, and the number of nodes in
Ψ0 is O(s · r2 ).
Since Ψ0 is in normal-homogenous-form, the nodes of Ψ0 are partitioned into 2r levels, according to
the type of node (i. e., a leaf, a sum-gate, or a product-gate) and its syntactic-degree, as follows:
• Level-1 contains the leaves, and recall that all the leaves are labelled by variables. Without loss of
generality, we can assume that every variable labels exactly one leaf.
• Level-2 contains the sum-gates of syntactic-degree 1.
• For every i ∈ {2, . . . , r}, Level-(2i − 1) contains the product-gates of syntactic-degree i.
• For every i ∈ {2, . . . , r}, Level-(2i) contains the sum-gates of syntactic-degree i.
• The nodes in Level-(2r) are the output-gates.
The children of every sum-gate in Level-(2i) are nodes from Level-(2i − 1). Without loss of gener-
ality, we can assume that the children of every sum-gate in Level-(2i) are all the nodes in Level-(2i − 1).
That is, there is an edge between every node in Level-(2i − 1) and every node in Level-(2i). Note that
this doesn’t increase the number of nodes.
Recall also that the out-degree of every sum-gate is at most 1, and the only sum-gates of out-degree 0
are the gates in Level-(2r).
Every product-gate in Level-(2i − 1) has exactly two children, one is a sum-gate in Level-(2 j) (for
some 0 < j < i) and the other is a sum-gate in Level-(2i − 2 j). Thus, we further partition the product-
gates in Level-(2i − 1) into i − 1 types (Type-1,...,Type-(i − 1)), according to the identity of that j.
If we knew the number of sum-gates in each (even) level, and the number of product-gates of each
type in each (odd) level, we could have constructed the circuit-graph GΨ0 , as follows:
• Level-1 contains n leaves, labelled by the n input variables.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 154
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
• The children of a sum-gate in Level-(2i) are all the nodes in Level-(2i − 1).
• The two children of a product-gate of Type- j in Level-(2i − 1) are a sum-gate in Level-(2 j) and a
sum-gate in Level-(2i − 2 j). The exact identity of these two sum-gates is not important. Just pick
arbitrary gates (in the right levels) that were still not used. They are all the same because they all
have the exact same children and they are all of out-degree 1.
Thus, in the circuit-graph G, we just have to make sure that we have enough nodes of each type in
each level. We can ensure that by having O(s · r2 ) nodes of each type in each level, a total number of
O(s · r4 ) nodes. Since we have enough nodes of each type in each level, we can embed the circuit graph
GΨ0 in G.
To construct the circuit Ψ, we use the circuit-graph G, and we just label by 0 every edge to or from
a node that is not in GΨ0 , and we label all other edges by their label in GΨ0 .
The following proposition will only be used in Section 5.
Proposition 2.9. For any integers n, s, r ≥ 3 such that s ≥ n, there is a circuit-graph G, in normal-
0 0
depth-4-form and of size at most O(s · n+rr0 −1 · r4 ) (and with O(s · n+rr0 −1 · r3 ) product-gates), where
r0 = b2r/3c, that is universal for n-inputs and one-output circuits of size s that compute homogenous
polynomials of degree r, in the following sense:
Let F be a field. Let Φ be an arithmetic circuit of size s, for a homogenous polynomial g ∈
F[x1 , . . . , xn ] of total-degree r. Then, there exists an arithmetic circuit Ψ, for the polynomial g, such
that GΨ = G.
0
Moreover, given n, s, r, the circuit-graph G can be constructed in time poly(s, n+rr0 −1 ).
Proof. Let F be a field. Let Φ be an arithmetic circuit of size s, for a homogenous polynomial g ∈
F[x1 , . . . , xn ] of total-degree r. By Proposition 2.7, there exists an arithmetic circuit Ψ0 , for the polyno-
0 0
mial g, such that Ψ0 is in normal-depth-4-form, and is of size O(s· n+rr0 −1 ·r3 ) (and has O(s· n+rr0 −1 ·r2 )
product-gates).
The circuit Ψ0 gives a presentation of g as a homogenous sum, g = ∑i Pi Qi , where Pi , Qi are homoge-
nous polynomials of degree at most r0 , and the sum is over at most O(s · r2 ) elements (see the proof of
Proposition 2.7).
Note that for every i, the sum of the degree of Pi (denoted, deg(Pi )) and the degree of Qi (denoted,
deg(Qi )) is exactly r. We can hence partition the pairs (Pi , Qi ) into O(r) types, acording to the degree
of Pi . As in the proof of Proposition 2.8, if we knew the number of pairs (Pi , Qi ) of each type, we could
have constructed the circuit-graph GΨ0 . This is true because in Ψ0 the polynomials Pi , Qi are computed
by a sum of all their monomials, and given deg(Pi ), deg(Qi ) this can be done by the same circuit-graph.
Thus, in the circuit-graph G, we just have to make sure that we have enough nodes that compute
Pi Qi of each of the O(r) types. We can ensure that by having O(s · r2 ) nodes of each type. Since we have
enough nodes of each type, we can embed the circuit graph GΨ0 in the circuit-graph G.
To construct the circuit Ψ, we use the circuit-graph G, and we just label by 0 every edge to or from
a node that is not in GΨ0 , and we label all other edges by their label in GΨ0 . 0
0
Note that the size of G is at most O(r) · O(s · n+rr0 −1 · r3 ) = O(s · n+rr0 −1 · r4 ) (and it has O(s ·
n+r0 −1
3
r0 · r ) product-gates).
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 155
R AN R AZ
3 Arithmetic circuits and polynomial mappings: Part I
In this section, we describe and prove our main results for polynomial mappings f that elude polyno-
mial-mappings Γ of degree larger than 2. The main results appear in Subsection 3.4.
3.1 Notation
Let F be a field. Let n, r be integers. 0
0 n+r−1
We fix m to be the number of monomials of total-degree exactly r
0 · n. Note that r is not necessarily a constant, and
in n variables, that is, m = r , and we fix m = m
may be a function of n. In general, we think of all parameters as functions of the basic parameter n. We
assume that 1 ≤ r ≤ n, and we assume for simplicity that n is a power of 2.
For an integer k, denote by [k] the set {1, . . . , k}, and denote by k̄ the binary representation of k − 1.
Let Z = {z1 , . . . , zn } be a set of n input variables. Let M be the set of all monomials of total-
degree exactly r in the variables {z1 , . . . , zn }. Note that |M| = m0 . We can identify the set M with
the set [m0 ], by the lexicographic order of monomials. Formally, let h : M → [m0 ] be the lexicographic
order of monomials. We can now identify the set M × [n] with the set [m0 · n] = [m], by the bijection
(q, i) → (h(q), i), where (here and later on) we think of (h(q), i) ∈ [m0 ] × [n] as an element of [m0 · n] = [m]
(by the lexicographic order).
We denote by M the set of all homogenous polynomials in F[Z] of total-degree exactly r. We identify
0
the vector space M = FM with the vector space F[m ] (by the bijection h between the bases). We will
consider tuples (g1 , . . . , gn ) ∈ Mn of n homogenous polynomials of total-degree exactly r. We identify
the vector space Mn = FM×[n] with the vector space Fm (by the bijection (q, i) → (h(q), i) between the
bases). Formally, we denote this homomorphism by
H : M n → Fm .
Intuitively, this means that we think of a vector in Fm as a tuple of n polynomials in M, and vice versa.
Each coordinate of the vector in Fm corresponds to the coefficient of one monomial in one of the n
polynomials.7
Denote by Gn,r , the set of homogenous circuit-graphs G (see Section 2), of syntactic-degree r, over
the set of input variables Z = {z1 , . . . , zn }, such that G has exactly n output-gates, and all output-gates in
G are sum-gates. For a circuit-graph G, denote by S(G), the number of edges in G that reach sum-gates.
3.2 The polynomial mapping ΓG : Fs → Fm
Let G ∈ Gn,r . That is, G is a homogenous circuit-graph, of syntactic-degree r, over the set of input
variables Z = {z1 , . . . , zn }, such that G has exactly n output-gates, and all output-gates in G are sum-
gates. Denote, s = S(G), that is, the number of edges in G that reach sum-gates. (Note that s ≥ n.)
Let Φ be an arithmetic circuit over F, with circuit-graph GΦ = G. Without loss of generality, we
assume that in the circuit Φ, all edges that reach product-gates are labelled by 1 (otherwise, if an edge
7 We consider a tuple of polynomials in M, rather than a single polynomial, because it will improve the parameters in some
of our results, by applying the result of Baur and Strassen [5] (see in the introduction). In Section 5, we work with a single
polynomial, (which is somewhat simpler).
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 156
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
that reaches a product-gate is labelled by α 6= 1, we just change its label to 1 and multiply the labels of
all edges that leave that product-gate by α). Denote the labels of the s edges that reach sum-gates by
y1 , . . . , ys .
The circuit Φ computes n homogenous polynomials in F[Z] of total-degree exactly r, (that is, a tuple
of n polynomials in M), where the coefficients in these polynomials depend on the labels y1 , . . . , ys . Since
we think of a tuple of n polynomials in M as a point in Fm , we obtain for every point (y1 , . . . , ys ) ∈ Fs , a
point in Fm .
Formally, we define a mapping ΓG : Fs → Fm , as follows. Given y1 , . . . , ys ∈ F, let Φ be an arithmetic
circuit over F, with circuit-graph GΦ = G, such that the labels of all edges that reach product-gates in Φ
are 1, and the labels of the s edges that reach sum-gates in Φ are y1 , . . . , ys . Denote the n polynomials
computed by Φ by g1 , . . . , gn ∈ M (note that these polynomials depend on the labels y1 , . . . , ys ). Define
ΓG (y1 , . . . , ys ) = H((g1 , . . . , gn )) .
Note that the n outputs of the circuit Φ can be viewed as polynomials in both z1 , . . . , zn and y1 , . . . , ys .
That is, we can think of g1 , . . . , gn as polynomials in the input variables z1 , . . . , zn , with coefficients
that are polynomials in the input variables y1 , . . . , ys . Therefore, the functions (ΓG )1 , . . . , (ΓG )m are
polynomials in F[y1 , . . . , ys ]. That is, ΓG is a polynomial mapping. Moreover, it is straightforward to
prove (formally, by induction on the circuit) that the polynomials (ΓG )1 , . . . , (ΓG )m do not depend on
the field F, but only on its characteristic (intuitively, this is obvious because all the coefficients in these
polynomials are derived by a sequence of sum and product operations on the constants 0,1, and are hence
members of the minimal subfield of F that contains 0,1).
Proposition 3.1. Let G ∈ Gn,r . For every g = (g1 , . . . , gn ) ∈ Mn , we have: H(g) ∈ Image(ΓG ) iff there
exists an arithmetic circuit Φ, (over F), with GΦ = G, for the n polynomials g1 , . . . , gn .
Proof. If H(g) ∈ Image(ΓG ) then obviously, by the definition of ΓG , there exists an arithmetic circuit
Φ, (over F), with GΦ = G, for the n polynomials g1 , . . . , gn .
If there exists an arithmetic circuit Φ, (over F), with GΦ = G, for the n polynomials g1 , . . . , gn ,
without loss of generality, we assume that in the circuit Φ, all edges that reach product-gates are labelled
by 1 (otherwise, if an edge that reaches a product-gate is labelled by α 6= 1, we just change its label to 1
and multiply the labels of all edges that leave that product-gate by α). Denote the labels of the s edges in
Φ that reach sum-gates by α1 , . . . , αs . Then, by the definition of ΓG , we have ΓG (α1 , . . . , αs ) = H(g).
Proposition 3.2. If G ∈ Gn,r is in normal-homogenous-form (see Definition 2.2), then the mapping ΓG :
Fs → Fm (where s = S(G) and m = n+r−1
r · n) is a (homogenous) polynomial mapping of degree 2r − 1.
r
Moreover, given G, one can construct ΓG in time poly(s ) in the following sense. There exists
a poly(sr )-time Turing machine, that on input G outputs (all the coefficients of) the m polynomials
(ΓG )1 , . . . , (ΓG )m ∈ F[y1 , . . . , ys ], and such that all the coefficients in these polynomials are integers8 in
{0, . . . , (3r)!}.
Proof. Let Φ be an arithmetic circuit over F, with circuit-graph GΦ = G, such that the labels of all edges
that reach product-gates are 1, and the labels of the s edges that reach sum-gates are y1 , . . . , ys .
8 Recall that we think of the integers as members of every field F, by the inductive definition n = (n − 1) + 1.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 157
R AN R AZ
For a node v in Φ, denote the polynomial (in the input variables Z), computed by the node v, by
gv ∈ F[Z], and denote by rv the syntactic-degree of v. Note that if v is a leaf, all the coefficients in gv
are in {0, 1}, and hence they do not depend on y1 , . . . , ys . By induction, we show that if v is a sum-gate
of syntactic-degree rv , then every coefficient in the polynomial gv ∈ F[Z] is a (homogenous) polynomial
of degree 2rv − 1 in the labels y1 , . . . , ys , and if v is a product-gate of syntactic-degree rv , then every
coefficient in the polynomial gv ∈ F[Z] is a (homogenous) polynomial of degree 2rv − 2 in the labels
y1 , . . . , ys .
The proof is straightforward. If v is a product-gate, with children v1 , v2 (that are sum-gates), then, by
induction, the coefficients in the polynomials gv1 , gv2 are (homogenous) polynomials of degrees 2rv1 −
1, 2rv2 − 1, respectively (in the labels y1 , . . . , ys ). Since the edges (v1 , v) and (v2 , v) are labelled by 1, the
coefficients in the polynomial gv are (homogenous) polynomials of degree 2rv1 − 1 + 2rv2 − 1 = 2rv − 2
(in the labels y1 , . . . , ys ).
If v is a sum-gate, then, by induction, the coefficients in the polynomial gu , for every child u of
v, are (homogenous) polynomials of degree 2ru − 2 = 2rv − 2 (in the labels y1 , . . . , ys ). Since the edge
(u, v) is labelled by an element of {y1 , . . . , ys }, the coefficients in the polynomial gv are (homogenous)
polynomials of degree 2rv − 1 (in the labels y1 , . . . , ys ).
As for the moreover part, denote Y = {y1 , . . . , ys } and think of Y, Z as two sets of input variables.
For a node v in Φ, denote the polynomial (in the input variables Y, Z), computed by the node v, by
.
g̃v ∈ F[Y, Z], and note that g̃v is a homogenous polynomial of degree r̃v = rv + (2rv − 1) = 3rv − 1, if v
.
is a sum-gate, and r̃v = rv + (2rv − 2) = 3rv − 2, if v is a product-gate, where rv is the syntactic-degree
of v in the circuit-graph G. Thus, each g̃v contains poly(sr ) monomials. Thus, we can work our way
up the circuit and compute all the coefficients in all the polynomials g̃v , in time poly(sr ). By induction,
all these coefficients are (positive) integers. By induction, we can show that the coefficients in each
polynomial g̃v are bounded by (r̃v )!. The induction is straightforward: When we have a sum-gate, we
always sum polynomials with disjoint sets of monomials, because the edges that reach the sum-gate are
labelled by different variables in Y , that were not used before. Thus, a sum-gate doesn’t increase the
coefficients. When we have a product-gate v, it multiplies v1 and v2 . By induction, the coefficients in
the polynomials g̃v1 , g̃v2 are bounded by (r̃v1 )!, (r̃v2 )!, respectively. Since each monomial in g̃v can be
obtained in at most (r̃v )!/((r̃v1 )! · (r̃v2 )!) different ways, from monomials in g̃v1 , g̃v2 , we obtain a bound
of (r̃v )! on its coefficient.
Proposition 3.3. For every n, r, m, s0 such that 1 ≤ r ≤ n ≤ s0 and m = n · n+r−1
r , there exists a circuit-
graph G ∈ Gn,r , with S(G) ≤ Size(G) = O((s ) · r ), such that:
0 2 8
1. G is in normal-homogenous-form. Hence, ΓG : Fs → Fm (where s = S(G)) is a (homogenous)
polynomial mapping of degree 2r − 1.
2. For every g = (g1 , . . . , gn ) ∈ Mn , if there exists an arithmetic circuit of size s0 (over F) for the n
polynomials g1 , . . . , gn , then H(g) ∈ Image(ΓG ).
3. For every g = (g1 , . . . , gn ) ∈ Mn , if H(g) ∈ Image(ΓG ), then there exists an arithmetic circuit Φ,
(over F), with GΦ = G, for the n polynomials g1 , . . . , gn .
Moreover, one can construct G, ΓG in time poly(sr ) in the following sense. There exists a poly(sr )-
time Turing machine, that on input n, r, s0 , outputs G and (all the coefficients of) the m polynomials
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 158
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
(ΓG )1 , . . . , (ΓG )m ∈ F[y1 , . . . , ys ], and such that all the coefficients in these polynomials are integers in
{0, . . . , (3r)!}.
Proof. Let G be the circuit-graph from Proposition 2.8, with parameters n, s0 , r, that is, a universal
circuit-graph for n-inputs and n-outputs circuits of size s0 that compute homogenous polynomials of
degree r. Denote s = S(G), and note that s ≤ Size(G) ≤ O((s0 )2 · r8 ). By Proposition 2.8, G is in normal-
homogenous-form, and note that G is of syntactic-degree r. Hence, by Proposition 3.2, ΓG : Fs → Fm is
a (homogenous) polynomial mapping of degree 2r − 1.
Let g = (g1 , . . . , gn ) ∈ Mn . Assume that there exists an arithmetic circuit of size s0 (over F) for
the n polynomials g1 , . . . , gn . Then, by Proposition 2.8, there exists an arithmetic circuit Φ, for the
polynomials g1 , . . . , gn , such that GΦ = G. Thus, by Proposition 3.1, H(g) ∈ Image(ΓG ).
The third claim is a special case of Proposition 3.1 (and is restated here for completeness). The
moreover part follows immediately from the moreover parts of Proposition 2.8 and Proposition 3.2.
Proposition 3.4. Let r = 1 and m = n2 . If G ∈ Gn,r is in normal-linear-form (see Definition 2.4), then
the mapping ΓG : Fs → Fm , (where s = S(G) = Size(G)), is a polynomial mapping of degree Depth(G).
Proof. Let Φ be an arithmetic circuit over F, with circuit-graph GΦ = G, such that the labels of the s
edges in G are y1 , . . . , ys .
For a node v in Φ, denote the linear polynomial (in the input variables Z), computed by the node v,
by gv ∈ F[Z]. Note that if v is a leaf, all the coefficients in gv are in {0, 1}, and hence they do not depend
on y1 , . . . , ys . By induction we show that if v is a gate of depth dv (i. e., the length of the longest directed
path that reaches v is dv ), then every coefficient in the polynomial gv ∈ F[Z] is a polynomial of degree at
most dv in the labels y1 , . . . , ys .
The proof is straightforward. If v is a gate of depth dv , then all children of v are of depth at most
dv − 1. Then, by induction, the coefficients in the polynomial gu , for every child u of v, are polynomials
of degree at most dv − 1 (in the labels y1 , . . . , ys ). Since the edge (u, v) is labelled by an element of
{y1 , . . . , ys }, the coefficients in the polynomial gv are polynomials of degree at most dv (in the labels
y1 , . . . , ys ).
3.3 The polynomial f˜
Let X = {x1 , . . . , xn } be an additional set of input variables. Let f = ( f1 , . . . , fm ), where f1 , . . . , fm ∈
F[x1 , . . . , xn ], be a polynomial mapping f : Fn → Fm . Intuitively, since we think of a point in Fm as a
tuple of n polynomials in the set of variables Z, we can think of f as a tuple of n polynomials in the sets
of variables X, Z.
Formally, given f , we define a tuple of n polynomials f˜1 , . . . , f˜n ∈ F[X, Z], by
f˜i (x1 , . . . , xn , z1 , . . . , zn ) = ∑ f(h(q),i) (x1 , . . . , xn ) · q = ∑ f( j,i) (x1 , . . . , xn ) · h−1 ( j)
q∈M j∈[m0 ]
(where, as before, we think of (h(q), i) and ( j, i) as elements of [m]). In other words, for every monomial
qx in the variables {x1 , . . . , xn } and monomial qz ∈ M, the coefficient of the monomial qx qz in f˜i is simply
the coefficient of the monomial qx in f(h(qz ),i) . (For monomials qx , qz such that qz 6∈ M, the coefficient of
the monomial qx qz in f˜i is 0.)
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 159
R AN R AZ
Finally, we define the polynomial f˜ as follows.9 Let W = {w1 , . . . , wn } be an additional set of input
variables. Define f˜ ∈ F[X, Z,W ], by
n
f˜(x1 , . . . , xn , z1 , . . . , zn , w1 , . . . , wn ) = ∑ wi · f˜i (x1 , . . . , xn , z1 , . . . , zn ) .
i=1
For a = (a1 , . . . , an ) ∈ Fn , denote by f˜1 |a , . . . , f˜n |a ∈ F[Z], the n polynomials f˜1 , . . . , f˜n ∈ F[X, Z], after
the substitution x1 = a1 , . . . , xn = an .
Proposition 3.5. ∀a ∈ Fn , we have, ( f˜1 |a , . . . , f˜n |a ) ∈ Mn , and H(( f˜1 |a , . . . , f˜n |a )) = f (a).
Proof. The proof is straightforward from the definitions. For every i ∈ [n] and a = (a1 , . . . , an ) ∈ Fn ,
f˜i |a (z1 , . . . , zn ) = f˜i (a1 , . . . , an , z1 , . . . , zn ) = ∑ f(h(q),i) (a) · q ∈ M .
q∈M
Thus,
H ( f˜1 |a , . . . , f˜n |a ) = H (∑q∈M f(h(q),1) (a) · q, . . . , ∑q∈M f(h(q),n) (a) · q)
= H (∑ j∈[m0 ] f( j,1) (a) · h−1 ( j), . . . , ∑ j∈[m0 ] f( j,n) (a) · h−1 ( j))
= f(1,1) (a), . . . , f(m0 ,n) (a) = f (a) .
Proposition 3.6. If f = ( f1 , . . . , fm ) is poly(n)-definable (see Definition 1.3), then the polynomial f˜ ∈
F[X, Z,W ] is poly(n)-definable.
Proof. We will show that for every i ∈ [n], the polynomial f˜i ∈ F[X, Z] is poly(n)-definable. Obviously,
this implies that the polynomial f˜ = ∑ni=1 wi · f˜i is poly(n)-definable.
First, we construct an arithmetic circuit C, of size and degree poly(n), that gets as input the variables
z1 , . . . , zn , u1 , . . . , u` (for some ` = poly(n)), and the binary representation j¯ (of j − 1), for an integer
0
j ∈ [m0 ], and such that for every j¯ ∈ {0, 1}log m ,
∑ C(z1 , . . . , zn , u1 , . . . , u` , j¯) = h−1 ( j) .
u1 ,...,u` ∈{0,1}
(For j 6∈ [m0 ], we define h−1 ( j) = 0.)
This is done by the following steps:
1. First construct a poly(n)-size Boolean circuit C1 that gets as input the binary representation j¯
and outputs r vectors (c1,1 , . . . , c1,n ), · · · , (cr,1 , . . . , cr,n ) ∈ {0, 1}n such that ∏ra=1 ∑nb=1 ca,b za,b =
h−1 ( j). That is, on input j¯, the circuit C1 generates a “description” of the monomial h−1 ( j) ∈ M.
Obviously, this can be done in poly(n) time, and hence such a circuit C1 exists. Denote by ` the
number of nodes in C1 .
9 The set W is introduced, and the polynomial f˜ is defined in this way, in order to make use of the result of Baur and
Strassen [5] (see in the introduction).
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 160
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
2. For every node in C1 , we introduce a variable in {0, 1} that represents the value computed at
that node. Let u1 , . . . , u` ∈ {0, 1} be these variables. We rename the variables corresponding to
the r · n output nodes by u1,1 , . . . , u1,n , · · · , ur,1 , . . . , ur,n (we think of these variables as having two
names). We can now construct a poly(n)-size Boolean formula C2 (in conjunctive-normal-form),
that gets as input the binary representation j¯ and the set of variables {u1 , . . . , u` } (including the
r · n output variables), and outputs 1 iff (u1 , . . . , u` ) is the correct computation of C1 on j¯. This is
done as in Cook-Levin’s proof for the NP-completeness of SAT . Note that if (u1 , . . . , u` ) is the
correct computation, then u1,1 , . . . , u1,n , · · · , ur,1 , . . . , ur,n are such that ∏ra=1 ∑nb=1 ua,b za,b = h−1 ( j).
Hence,
r n
∑ C2 (u1 , . . . , u` , j¯) · ∏ ∑ ua,b za,b = h−1 ( j) .
u1 ,...,u` ∈{0,1} a=1 b=1
Since any polynomial-size Boolean formula can be easily translated into an arithmetic formula of
polynomial size and degree, we can think of C2 as an arithmetic circuit of size and degree poly(n).
3. Finally, we define the arithmetic circuit C by,
r n
C(z1 , . . . , zn , u1 , . . . , u` , j¯) = C2 (u1 , . . . , u` , j¯) · ∏ ∑ ua,b za,b .
a=1 b=1
Recall that for an integer k, we denote by k̄ the binary representation of k − 1. Note that since we
assumed that n is a power of 2, the binary representation ( j, i), for ( j, i) ∈ [m], is simply ( j¯, ī) (where, as
before, we think of ( j, i) ∈ [m0 ] × [n] as an element of [m] by the lexicographic order).
Since the polynomial mapping f : Fn → Fm is poly(n)-definable, for some `0 = poly(n), there is an
arithmetic circuit D, of size and degree poly(n), that gets as input variables x1 , . . . , xn , e1 , . . . , e`0 , and the
binary representations j¯, ī (for j ∈ [m0 ], i ∈ [n]), and such that for every ( j, i) ∈ [m],
f( j,i) (x1 , . . . , xn ) = ∑ D(x1 , . . . , xn , e1 , . . . , e`0 , j¯, ī) .
e1 ,...,e`0 ∈{0,1}
We can now write, for every i ∈ [n],
f˜i (x1 , . . . , xn , z1 , . . . , zn ) = ∑ f( j,i) (x1 , . . . , xn ) · h−1 ( j) =
j∈[m0 ]
∑ ∑ D(x1 , . . . , xn , e1 , . . . , e`0 , j¯, ī) · ∑ C(z1 , . . . , zn , u1 , . . . , u` , j¯) .
j∈[m0 ] e1 ,...,e`0 ∈{0,1} u1 ,...,u` ∈{0,1}
0
Since we can replace the sum over j ∈ [m0 ] by a sum over j¯ ∈ {0, 1}log m , the polynomial f˜i is poly(n)-
definable, by the definition of poly(n)-definability.
3.4 The route to lower bounds
In this subsection, we prove our main results for polynomial mappings f that elude polynomial mappings
Γ of degree larger than 2. The results are given by five propositions and corollaries. Proposition 3.7,
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 161
R AN R AZ
Corollary 3.8, Corollary 3.9 and Corollary 3.10 give the connection for general arithmetic circuits. Note
that these four propositions and corollaries are only interesting for r ≥ 2, (although, to avoid confusion,
they are stated for r ≥ 1). Proposition 3.11 gives the connection for arithmetic circuits of depth d, and is
the one used to prove our lower bounds for bounded-depth arithmetic circuits. All five propositions and
corollaries are only interesting for s < m (although this condition is not stated explicitly).
Recall that we think of all the parameters (r, s, m, etc.) as functions of the basic parameter n.
Recall that given a polynomial mapping f : Fn → Fm , and given a field extension G ⊃ F, we can
think of f as a polynomial mapping f : Gn → Gm . This is because we assume that a polynomial mapping
f : Fn → Fm is given as a tuple ( f1 , . . . , fm ) of polynomials in F[x1 , . . . , xn ] ⊂ G[x1 , . . . , xn ] (see the
discussion in Subsection 1.4).
Proposition 3.7. For integers 1 ≤ r ≤ n ≤ s0 , and m = n · n+r−1 , let ΓG : Fs → Fm (where s = O((s0 )2 ·
r
8
r )) be the (homogenous) polynomial mapping of degree 2r − 1 from Proposition 3.3. Let f : Fn → Fm
be a polynomial mapping.
If over some field extension G ⊇ F,
Image( f : Gn → Gm ) 6⊂ Image(ΓG : Gs → Gm ) ,
then any arithmetic circuit (over F) for the polynomial f˜ : F3n → F (explicitly defined from f in Subsec-
tion 3.3), is of size > s0 /5.
Proof. Let us first prove the proposition for G = F.
By Proposition 3.3, for every (g1 , . . . , gn ) ∈ Mn , if there exists an arithmetic circuit of size s0 (over F)
for the n polynomials g1 , . . . , gn , then H((g1 , . . . , gn )) ∈ Image(ΓG ).
Assume for a contradiction that there exists an arithmetic circuit (over F) of size s0 /5, for the poly-
nomial f˜ : F3n → F. Baur and Strassen proved that if a polynomial ( f˜) can be computed by an arithmetic
circuit of size s00 , then all partial derivatives of that polynomial can be computed by one arithmetic cir-
cuit of size 5s00 [5] (for an improvement of the constant see [18]). By the result of Baur and Strassen,
there is an arithmetic circuit of size s0 for the n polynomials f˜1 , . . . , f˜n : F2n → F. By substituting in this
circuit x1 = a1 , . . . , xn = an , where a = (a1 , . . . , an ) ∈ Fn , we obtain an arithmetic circuit of size s0 for
the n polynomials f˜1 |a , . . . , f˜n |a , and note that by Proposition 3.5, f˜1 |a , . . . , f˜n |a ∈ M. Hence, by Proposi-
tion 3.3, (for every a1 , . . . , an ∈ F), H(( f˜1 |a , . . . , f˜n |a )) ∈ Image(ΓG ). Thus, by Proposition 3.5, for every
a1 , . . . , an ∈ F,
f (a1 , . . . , an ) = H(( f˜1 |a , . . . , f˜n |a )) ∈ Image(ΓG ) .
That is,
Image( f ) ⊂ Image(ΓG ) .
Assume now that G is a general field, extending F, and assume that
Image( f : Gn → Gm ) 6⊂ Image(ΓG : Gs → Gm ) .
By the part that we already proved (i. e., the case G = F), we know that any arithmetic circuit over G,
for the polynomial f˜, is of size > s0 /5. But any arithmetic circuit over F is in particular an arithmetic
circuit over G. Thus, any arithmetic circuit over F for the polynomial f˜ is of size > s0 /5. (Formally,
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 162
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
we need to verify that the polynomials f˜ and (ΓG )1 , . . . , (ΓG )m remain the same polynomials when we
work over G, rather than over F. This can be easily verified. For (ΓG )1 , . . . , (ΓG )m , it was noted after the
definition of ΓG that they do not depend on the field at all, but only on its characteristic. As for f˜, by its
definition, its coefficients are just corresponding coefficients from the polynomials f1 , . . . , fm , and hence
they do not depend on the field G.)
Corollary 3.8. Let 1 ≤ r ≤ n ≤ s, and m = n · n+r−1
r be integers. Let f : Fn → Fm be a polynomial
mapping. If over some field extension G ⊇ F, f is (s, (2r − 1))-elusive (see Definition 1.1), then any
arithmetic circuit (over F) for the polynomial f˜ : F3n → F (explicitly defined from f in Subsection 3.3),
√
is of size ≥ Ω( s/r4 ).
√
Proof. The proof follows immediately from Proposition 3.7. Let s0 = c · s/r4 , where c is a small
enough constant. If f is (s, (2r − 1))-elusive, then in particular it satisfies Image( f ) 6⊂ Image(ΓG ),
where ΓG is the mapping from Proposition 3.7.
Corollary 3.9. Let F be a field of characteristic not equal to 2. Let 1 ≤ r ≤ n ≤ s, and m = n · n+r−1
r
be integers such that s = nω(1) . If there exists a poly(n)-definable polynomial mapping f : Fn → Fm such
that, over some field extension G ⊇ F, f is (s, (2r − 1))-elusive (see Definition 1.3 and Definition 1.1),
then any arithmetic circuit for the permanent over F is of size ≥ sΩ(1) .
Proof. Assume that such a polynomial mapping f exists. By Proposition 3.6, and Corollary 3.8, the
polynomial f˜ : F3n → F (explicitly defined from f in Subsection 3.3) is poly(n)-definable, and any
arithmetic circuit (over F) for f˜ is of size ≥ sΩ(1) .
Valiant proved that over any field of characteristic not equal to 2, the permanent is a complete
polynomial for the class VNP of poly(n)-definable polynomials [36] (see also [10, 6]). Hence, any
arithmetic circuit of size s0 for the permanent implies an arithmetic circuit of size poly(s0 ) for any other
poly(n)-definable polynomial. Hence, any arithmetic circuit for the permanent over F is of size s0 ≥
sΩ(1) .
Corollary 3.10. Let 1 ≤ r ≤ n ≤ s, and m = n · n+r−1
r be integers (and recall that we think of r, s, m as
r
functions of n). Assume that there exists a poly(s )-time Turing machine T such that:
• The inputs for T are r, n, s, m and a (homogenous) polynomial mapping Γ : Fs → Fm of degree
2r − 1, given by all coefficients of the polynomials Γ1 , . . . , Γm (that are assumed to be integers10
in, say, {0, . . . , (3r)!}).
• The output of T is a poly(n)-definable polynomial mapping f : Fn → Fm (described, e. g., by an
arithmetic circuit for the polynomial g that defines it in Definition 1.3) such that, over some field
extension G ⊇ F,
Image( f : Gn → Gm ) 6⊂ Image(Γ : Gs → Gm ) .
Then, there exists a poly(sr )-time Turing machine that on input n outputs a 3n-variables, poly(n)-
definable, polynomial f˜ (explicitly defined from f in Subsection 3.3, and described, e. g., by an arithmetic
circuit for the polynomial g that defines it in Definition 1.3), such that any arithmetic circuit for f˜ is of
√
size ≥ Ω( s/r4 ).
10 Recall that we think of the integers as members of every field, by the inductive definition n = (n − 1) + 1.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 163
R AN R AZ
√
Proof. The proof follows immediately from Proposition 3.7. Let s0 = c · s/r4 , where c is a small
enough constant. We run the Turing machine T on the polynomial mapping Γ = ΓG , where ΓG is the
mapping from Proposition 3.7. Note that by Proposition 3.3, ΓG can be constructed in time poly(sr ) (for
details, see Proposition 3.3).
Proposition 3.11. Let n, d ≤ s, and m = n2 be integers. Let f : Fn → Fm be a polynomial mapping.
If over some field extension G ⊇ F, f is (s, d)-elusive (see Definition 1.1), then any depth-d arithmetic
circuit (over F) for the n polynomials f˜1 , . . . , f˜n : F2n → F (explicitly defined from f in Subsection 3.3,
(using r = 1)), is of size > s. (Note that the degree of each f˜i is at most the degree of f plus 1.)
Proof. Let us first prove the proposition for G = F.
Let X = {x1 , . . . , xn } and Z = {z1 , . . . , zn } be two sets of input variables.
Let F(X) = F(x1 , . . . , xn ) be the field of rational functions in the variables {x1 , . . . , xn }, over F. Let
f˜1 , . . . , f˜n ∈ F[X, Z] be the polynomials explicitly defined from f in Subsection 3.3, using r = 1. Note
that the total-degree of these polynomials in the set of variables Z is 1 (by the definition of f˜1 , . . . , f˜n ).
We can think of the polynomials f˜1 , . . . , f˜n as members of the ring of polynomials F(X)[z1 , . . . , zn ], that
is, polynomials in the set of variables Z, over the field F(X). Note, that f˜1 , . . . , f˜n ∈ F(X)[Z] are linear
polynomials (as their total-degree in the set of variables Z is 1).
Assume for a contradiction that there exists an arithmetic circuit Φ, over F, of depth d and size
s, for the n polynomials f˜1 , . . . , f˜n ∈ F[X, Z]. We can think of Φ as an arithmetic circuit for f˜1 , . . . , f˜n ,
over the field F(X) and set of input variables Z, i. e., an arithmetic circuit for f˜1 , . . . , f˜n ∈ F(X)[Z].
By Proposition 2.5, we can assume without loss of generality that Φ is in normal-linear-form, (see
Definition 2.4). That is, there is an arithmetic circuit Ψ, of depth d and size s, in normal-linear-form,
that computes f˜1 , . . . , f˜n , over the field F(X) and set of input variables Z. Moreover, by the proof of
Proposition 2.5, we can assume that the labels of the edges in Ψ are polynomials in F[X], rather than
rational functions in F(X). (This is true because in the proof of Proposition 2.5, the labels of the edges
in Ψ are defined from the labels of the edges in Φ without using divisions.) Denote by G = GΨ , the
circuit graph of Ψ (see Definition 2.1).
By Proposition 3.4, the mapping ΓG : Fs → Fm is a polynomial mapping of degree d. Hence, since
f is (s, d)-elusive, there exists (a1 , . . . , an ) ∈ Fn such that f (a1 , . . . , an ) 6∈ Image(ΓG ).
By substituting in the circuit Ψ the values x1 = a1 , . . . , xn = an , we obtain an arithmetic circuit of
size s and depth d, over F, with circuit-graph G, for the n polynomials f˜1 |a , . . . , f˜n |a ∈ F[Z]. (Note that
when we substitute x1 = a1 , . . . , xn = an , we do not introduce divisions-by-zero, because the labels of
the edges in Ψ are polynomials in F[X], rather than rational functions in F(X).) Note that by Propo-
sition 3.5, f˜1 |a , . . . , f˜n |a ∈ M. Hence, by Proposition 3.1, H(( f˜1 |a , . . . , f˜n |a )) ∈ Image(ΓG ). Hence, by
Proposition 3.5, f (a1 , . . . , an ) = H(( f˜1 |a , . . . , f˜n |a )) ∈ Image(ΓG ), which is a contradiction.
Assume now that G is a general field, extending F, and assume that f is (s, d)-elusive over G. By
the part that we already proved (i. e., the case G = F), we know that any depth-d arithmetic circuit, over
G, for the n polynomials f˜1 , . . . , f˜n is of size > s. But any arithmetic circuit over F is in particular an
arithmetic circuit over G. Thus, any depth-d arithmetic circuit, over F, for the n polynomials f˜1 , . . . , f˜n
is of size > s. (Formally, as before, we need to verify that the polynomials f˜1 , . . . , f˜n remain the same
polynomials when we work over G, rather than over F. This can be easily verified, as by the definition
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 164
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
of f˜1 , . . . , f˜n , their coefficients are just the corresponding coefficients from the polynomials f1 , . . . , fm ,
and hence they do not depend on the field.)
4 Lower bounds for bounded-depth circuits
4.1 A construction of an elusive polynomial mapping
For an integer k, denote by [k] the set {1, . . . , k}. Let n be a prime, and let m = n2 . We identify the set
[m] with [n] × [n] (by the lexicographic order). Let 1 ≤ d ≤ (log2 n)/100 be an integer. Let d 0 = 5d. Let
X = {xi, j }i∈[d 0 ], j∈[n] be a set of n ·d 0 input variables. For every (a, b) ∈ [n]×[n] = [m], define a polynomial
d0
f(a,b) (x1,1 , . . . , x
d 0 ,n ) = ∏ xi,a+i·b
i=1
where the sum a + i · b (as well as all other sums of this sort that appear below), is taken modulo n.
Let f = ( f(1,1) , f(1,2) , . . . , f(n,n) ). Note that for every field G, we can view f as a polynomial mapping
0
f : Gn·d → Gm .
Lemma 4.1. Let n be a prime, and let m = n2 . Let d be an integer such that 1 ≤ d ≤ (log2 n)/100. Let
d 0 = 5d. Let G be a field of size larger than m (e. g., an infinite field). Then, the polynomial mapping
0
f : Gn·d → Gm (as defined above) is (s, d)-elusive (see Definition 1.1), where s = bn1+1/(2d) c.
Proof. Let r = bn1−1/(2d) c. For a set Q ⊂ [n] × [n], denote
fQ = ∏ f(a,b) = ∏ ∏ xi,a+i·b .
(a,b)∈Q (a,b)∈Q i∈[d 0 ]
We say that Q ⊂ [n] × [n] is retrievable, if fQ determines Q, that is, Q is retrievable if for every Q0 6= Q,
we have fQ0 6= fQ .
Claim 4.2. Let Q ⊂ [n] × [n] be a random subset of size r. Then, with probability at least a half, Q is
retrievable.
Proof. Let us first prove the following claim.
Claim 4.3. If for every (a, b) ∈ [n] × [n] \ Q, at least one of the variables in {xi,a+i·b }i∈[d 0 ] doesn’t appear
in the monomial fQ , then the set Q is retrievable.
Proof. Let Q0 ⊂ [n] × [n] be such that fQ0 = fQ . We will show that Q0 = Q.
For every (a, b) ∈ [n] × [n] \ Q, at least one of the variables in {xi,a+i·b }i∈[d 0 ] doesn’t appear in the
monomial fQ = fQ0 , and hence (a, b) 6∈ Q0 . Thus Q0 ⊆ Q. Since the total-degrees of fQ and fQ0 are the
same, |Q0 | = |Q|. Hence, Q0 = Q.
It is hence enough to show that with probability (over Q) at least 1/2, for every (a, b) ∈ [n] × [n] \ Q,
at least one of the variables in {xi,a+i·b }i∈[d 0 ] doesn’t appear in the monomial fQ .
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 165
R AN R AZ
A variable xi, j appears in the monomial fQ iff there exists (a0 , b0 ) ∈ Q such that j = a0 + i · b0 . Hence,
a variable xi,a+i·b appears in the monomial fQ iff there exists (a0 , b0 ) ∈ Q such that a + i · b = a0 + i · b0 ,
that is, (a0 − a) + i · (b0 − b) = 0. Denote by `a,b,i the line {(a0 , b0 ) ∈ [n] × [n] : (a0 − a) + i · (b0 − b) = 0}.
Thus, a variable xi,a+i·b appears in the monomial fQ iff Q ∩ `a,b,i 6= 0. /
Thus, for (a, b) ∈ [n] × [n], the statement “at least one of the variables in {xi,a+i·b }i∈[d 0 ] doesn’t appear
in the monomial fQ ” is equivalent to the statement “there exists i ∈ [d 0 ] such that Q ∩ `a,b,i = 0.” /
Fix (a, b) ∈ [n] × [n]. Note that for different i1 , i2 ∈ [d 0 ], the two lines `a,b,i1 , `a,b,i2 intersect only at
the point (a, b). Hence, the probability over Q, such that (a, b) 6∈ Q, for the event: “for every i ∈ [d 0 ],
Q ∩ `a,b,i 6= 0,”
/ is at most
0
|Q| · (n − 1) d
0
2
≤ n−d /(2d) ≤ n−2 /2 .
(n − 1)
Thus, for every (a, b) ∈ [n] × [n], the probability, over Q, for the event: “(a, b) 6∈ Q, and for every
i ∈ [d 0 ], Q ∩ `a,b,i 6= 0”
/ is at most n−2 /2. By the union bound, with probability (over Q) at most 1/2,
there exists (a, b) ∈ [n] × [n], such that: (a, b) 6∈ Q, and for every i ∈ [d 0 ], Q ∩ `a,b,i 6= 0.
/ Thus, with
probability (over Q) at least 1/2, for every (a, b) ∈ [n] × [n], either (a, b) ∈ Q, or there exists i ∈ [d 0 ] such
that Q ∩ `a,b,i = 0./
Thus, with probability at least 1/2, the set Q is retrievable. (End of proof of Claim 4.2.)
Denote by L the set of all multilinear homogenous polynomials Λ : Gm → G of total-degree exactly r,
such that every monomial that appears in Λ (with coefficient not equal to 0) corresponds to a retrievable
set Q ⊂ [n] × [n] = [m]. Thus, by Claim 4.2, L is a vector space (over G), of dimension ≥ mr /2 ≥
m r
r ≥ sr (where the second inequality holds since m, r are large enough, by the assumptions of the
lemma).
0
Claim 4.4. For every Λ ∈ L, other than the 0 polynomial, the polynomial Λ ◦ f : Gn·d → G is not the 0
polynomial.
0
Proof. Λ ◦ f : Gn·d → G is a linear combination of monomials fQ (in the n · d 0 variables {xi, j }i∈[d 0 ], j∈[n] ),
where Q ⊂ [n] × [n] is a retrievable set of size r. Since for every two different retrievable sets Q1 , Q2 ,
the monomials fQ1 , fQ2 are different monomials (in the n · d 0 variables {xi, j }i∈[d 0 ], j∈[n] ), there are no
cancellations of monomials, and hence the polynomial Λ ◦ f cannot be the 0 polynomial.
Fix Γ : Gs → Gm to be a polynomial mapping of degree d. Thus, for every Λ ∈ L, the polynomial
Λ ◦ Γ : Gs → G is of total-degree at most r · d.
Denote by K the set of all polynomials from Gs to G of total-degree at most r · d. Thus, K is a vector
space (over G), of dimension no more than
s + r d (s + r)r·d (2s)r·d 2es r·d
≤ ≤ ≤ ≤ (6n)r < sr .
r (r!)d (r/e)r·d r
For a fixed Γ : Gs → Gm (of degree d), the mapping Λ → Λ ◦ Γ (where Λ ∈ L) is a linear mapping
from L to K. Hence, since dim(L) > dim(K), there exist Λ 6= 0 such that Λ ◦ Γ = 0. Fix ΛΓ to be that
Λ.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 166
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
By Claim 4.4, ΛΓ ◦ f is not the 0 polynomial. Hence, since |G| ≥ m and since the degree of ΛΓ ◦ f is
0
smaller than m, the function ΛΓ ◦ f : Gn·d → G is not the 0 function. Since the function ΛΓ ◦ Γ is the 0
function, Image( f ) 6⊂ Image(Γ).
Since this is true for every polynomial mapping Γ : Gs → Gm , of degree d, the polynomial mapping
f is (s, d)-elusive, by definition. (End of proof of Lemma 4.1.)
4.2 The lower bound
Let n be a prime. Let 1 ≤ d ≤ (log2 n)/100 be an integer. Let d 0 = 5d. Let {xi, j }i∈[d 0 ], j∈[n] be a set of
n · d 0 input variables. For every (a, b) ∈ [n] × [n], define (as in Subsection 4.1),
f(a,b) (x1,1 , . . . , xd 0 ,n ) = ∏ xi,a+i·b
i∈[d 0 ]
(where the sum a + i · b is taken modulo n).
Let {z1 , . . . , zn }, {w1 , . . . , wn }, be two sets of input variables. Define, for every a ∈ [n],
f˜a = ∑ zb · f(a,b) .
b∈[n]
Define
f˜ = ∑ wa · f˜a .
a∈[n]
Note that these definitions are consistent with the definitions in Subsection 3.3.
Note that every f˜a is a polynomial in n · (d 0 + 1) variables, and is of total-degree d 0 + 1, and f˜ is a
polynomial in n · (d 0 + 2) variables, and is of total-degree d 0 + 2.
Corollary 4.5. Let n be a prime, and let 1 ≤ d ≤ (log2 n)/100 be an integer. Any depth-d arithmetic
circuit, over any field F, for the n polynomials (of total-degree 5d + 1 each) f˜1 , . . . , f˜n : Fn·(5d+1) → F (as
defined above), is of size ≥ n1+1/(2d) .
Proof. Let G be an infinite field extending F.
The proof follows immediately by Proposition 3.11, Lemma 4.1, and the trivial observation that an
(s, d)-elusive polynomial mapping stays (s, d)-elusive, when padded by zeros.
Corollary 4.6. Let n be a prime, and let 1 ≤ d ≤ (log2 n)/100 be an integer. Any depth-bd/3c arithmetic
circuit, over any field F, for the polynomial (of total-degree 5d + 2) f˜ : Fn·(5d+2) → F (as defined above),
is of size ≥ n1+1/(2d) /5.
Proof. Baur and Strassen proved that if a polynomial ( f˜) can be computed by an arithmetic circuit of
size s0 and depth d 0 , then all partial derivatives of that polynomial can be computed by one arithmetic
circuit of size 5s0 and depth 3d 0 [5] (for an improvement of the constants see [18]).
Thus the proof follows immediately by Corollary 4.5.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 167
R AN R AZ
5 Arithmetic circuits and polynomial mappings: Part II
In this section, we describe and prove our main results for polynomial-mappings f that elude polyno-
mial-mappings Γ of degree 2. The main results appear in Subsection 5.4. The description follows closely
the one in Section 3 but is somewhat simpler since here we consider a single polynomial g, rather than
a tuple of polynomials.
5.1 Notation
Let F be a field. Let n, r be integers. We fix m to be the number of monomials of total-degree exactly r
in n variables, that is, m = n+r−1 r . Note that r is not necessarily a constant, and may be a function of n.
In general, we think of all parameters as functions of the basic parameter n. We assume that 3 ≤ r ≤ n,
and we assume for simplicity that n is a power of 2. For an integer k, denote by [k] the set {1, . . . , k}.
Let Z = {z1 , . . . , zn } be a set of n input variables. Let M be the set of all monomials of total-degree
exactly r in the variables {z1 , . . . , zn }. Note that |M| = m. We can identify the set M with the set
[m], by the lexicographic order of monomials. Formally, let h : M → [m] be the lexicographic order of
monomials.
We denote by M the set of all homogenous polynomials in F[Z] of total-degree exactly r. We identify
the vector space M = FM with the vector space F[m] (by the bijection h between the bases). Formally,
we denote this homomorphism by
H : M → Fm .
Intuitively, this means that we think of a vector in Fm as a polynomial in M, and vice versa. Each
coordinate of the vector in Fm corresponds to the coefficient of one monomial in the polynomial.
Denote by Dn,r , the set of homogenous circuit-graphs G (see Section 2), of syntactic-degree r, over
the set of input variables Z = {z1 , . . . , zn }, such that G has a single output-gate and is in normal-depth-4-
form (see Section 2). For a circuit-graph G ∈ Dn,r , denote by S(G), the number of product-gates in G at
the level above the leaves (that is, the number of product-gates that are connected by an edge to a leaf).
5.2 The polynomial mapping ΓG : Fs → Fm
Let G ∈ Dn,r . That is, G is a homogenous circuit-graph, of syntactic-degree r, over the set of input
variables Z = {z1 , . . . , zn }, such that G has a single output-gate, and is in normal-depth-4-form. Denote,
s = S(G), that is, the number of product-gates in G at the level above the leaves. (Assume without loss
of generality that s ≥ n.)
Let Φ be an arithmetic circuit over F, with circuit-graph GΦ = G. Without loss of generality, we
assume that in the circuit Φ, all edges are labelled by 1, except for the edges that leave product-gates
at the level above the leaves. (Otherwise, if an edge that reaches a product-gate at the level above the
leaves is labelled by α 6= 1, we just change its label to 1 and multiply the label of the edge that leaves
that product-gate by α. Also, since G is a tree, we can assume without loss of generality that edges at
upper levels are labelled by 1.) Denote the labels of the s edges that leave product-gates at the level
above the leaves by y1 , . . . , ys .
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 168
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
(Intuitively, since Φ is in normal-depth-4-form, its computation can be presented as a homogenous
sum, ∑i Pi Qi , where Pi , Qi are homogenous polynomials of degree at most 2r/3. Intuitively, the labels
y1 , . . . , ys are just the coefficients of all the monomials in all the polynomials Pi , Qi .)
The circuit Φ computes a homogenous polynomial in F[Z] of total-degree exactly r, (that is, a poly-
nomials in M), where the coefficients in this polynomial depend on the labels y1 , . . . , ys . Since we think
of a polynomial in M as a point in Fm , we obtain for every point (y1 , . . . , ys ) ∈ Fs , a point in Fm .
Formally, we define a mapping ΓG : Fs → Fm , as follows. Given y1 , . . . , ys ∈ F, let Φ be an arithmetic
circuit over F, with circuit-graph GΦ = G, such that the labels of all edges in Φ are 1, except for edges
that leave product-gates at the level above the leaves, and the labels of the s edges that leave product-
gates at the level above the leaves are y1 , . . . , ys . Denote the polynomial computed by Φ by g ∈ M (note
that this polynomial depends on the labels y1 , . . . , ys ). Define
ΓG (y1 , . . . , ys ) = H(g) .
Note that the output of the circuit Φ can be viewed as a polynomial in both z1 , . . . , zn and y1 , . . . , ys .
That is, we can think of g as a polynomial in the input variables z1 , . . . , zn , with coefficients that are
polynomials in the input variables y1 , . . . , ys . Therefore, the functions (ΓG )1 , . . . , (ΓG )m are polynomials
in F[y1 , . . . , ys ]. That is, ΓG is a polynomial mapping. Moreover, it is straightforward to prove (formally,
by induction on the circuit) that the polynomials (ΓG )1 , . . . , (ΓG )m do not depend on the field F, but
only on its characteristic (intuitively, this is obvious because all the coefficients in these polynomials are
derived by a sequence of sum and product operations on the constants 0,1, and are hence members of
the minimal subfield of F that contains 0,1).
Proposition 5.1. Let G ∈ Dn,r . For every g ∈ M, we have: H(g) ∈ Image(ΓG ) iff there exists an
arithmetic circuit Φ, (over F), with GΦ = G, for the polynomial g.
Proof. If H(g) ∈ Image(ΓG ) then obviously, by the definition of ΓG , there exists an arithmetic circuit
Φ, (over F), with GΦ = G, for the polynomial g.
If there exists an arithmetic circuit Φ, (over F), with GΦ = G, for the polynomial g, without loss
of generality, we assume that in the circuit Φ, all edges are labelled by 1, except for edges that leave
product-gates at the level above the leaves.
Denote the labels of the s edges in Φ that leave product-gates at the level above the leaves by
α1 , . . . , αs . Then, by the definition of ΓG , we have ΓG (α1 , . . . , αs ) = H(g).
Proposition 5.2. Let G ∈ Dn,r . Then, the mapping ΓG : Fs → Fm (where s = S(G) and m = n+r−1
r ) is
a (homogenous) polynomial mapping of degree 2.
Moreover, given G, one can construct ΓG in time poly(s, m) in the following sense. There exists
a poly(s, m)-time Turing machine, that on input G outputs (all the coefficients of) the m polynomials
(ΓG )1 , . . . , (ΓG )m ∈ F[y1 , . . . , ys ], and such that all the coefficients in these polynomials are in {0, 1}.
Proof. Let Φ be an arithmetic circuit over F, with circuit-graph GΦ = G, such that in Φ, all edges are
labelled by 1, except for edges that leave product-gates at the level above the leaves, and the labels of
the s edges that leave product-gates at the level above the leaves are y1 , . . . , ys .
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 169
R AN R AZ
Since Φ is in normal-depth-4-form, its computation can be presented as a homogenous sum, g =
∑i Pi Qi , where Pi , Qi are homogenous polynomials of degree at most 2r/3. Note that the labels y1 , . . . , ys
are just the coefficients of all the monomials in all the polynomials Pi , Qi .
Thus, the coefficients of the monomials of g are homogenous polynomials of degree 2 in the labels
y1 , . . . , ys , and are in {0, 1}. Moreover, these coefficients can be computed in time polynomial in s, m.
Proposition 5.3. For every n, r, m, s0 such that 3 ≤ r ≤ n ≤ s0 and m = n+r−1
r , there exists a circuit-
n+r0 −1 n+r0 −1
graph G ∈ Dn,r , with S(G) = O(s · 0 0 · r ), where r0 = b2r/3c,
3 4
r0 · r ), and Size(G) = O(s · r0
such that:
1. ΓG : Fs → Fm (where s = S(G)) is a (homogenous) polynomial mapping of degree 2.
2. For every g ∈ M, if there exists an arithmetic circuit of size s0 (over F) for the polynomial g, then
H(g) ∈ Image(ΓG ).
3. For every g ∈ M, if H(g) ∈ Image(ΓG ), then there exists an arithmetic circuit Φ, (over F), with
GΦ = G, for the polynomial g.
Moreover, one can construct G, ΓG in time poly(s, m) in the following sense. There exists a poly(s, m)-
time Turing machine, that on input n, r, s0 , outputs G and (all the coefficients of) the m polynomials
(ΓG )1 , . . . , (ΓG )m ∈ F[y1 , . . . , ys ], and such that all the coefficients in these polynomials are in {0, 1}.
Proof. Let G be the circuit-graph from Proposition 2.9, with parameters n, s0 , r, that is, a universal
circuit-graph for n-inputs and one-output circuits of size s0 that
compute homogenous polynomials 4of
0 n+r0 −1 3 0 n+r0 −1
degree r. Denote s = S(G), and note that S(G) = O(s · r0 · r ), and Size(G) = O(s · r0 · r ).
By Proposition 2.9, G is in normal-depth-4-form, and note that G is of syntactic-degree r. Hence, by
Proposition 5.2, ΓG : Fs → Fm is a (homogenous) polynomial mapping of degree 2.
Let g ∈ M. Assume that there exists an arithmetic circuit of size s0 (over F) for the polynomial g.
Then, by Proposition 2.9, there exists an arithmetic circuit Φ, for the polynomial g, such that GΦ = G.
Thus, by Proposition 5.1, H(g) ∈ Image(ΓG ).
The third claim is a special case of Proposition 5.1 (and is restated here for completeness). The
moreover part follows immediately from the moreover parts of Proposition 2.9 and Proposition 5.2.
5.3 The polynomial f˜
Let X = {x1 , . . . , xn } be an additional set of input variables. Let f = ( f1 , . . . , fm ), where f1 , . . . , fm ∈
F[x1 , . . . , xn ], be a polynomial mapping f : Fn → Fm . Intuitively, since we think of a point in Fm as a
polynomial in the set of variables Z, we can think of f as a polynomial in the sets of variables X, Z.
Formally, given f , we define a polynomial f˜ ∈ F[X, Z], by
f˜(x1 , . . . , xn , z1 , . . . , zn ) = ∑ fh(q) (x1 , . . . , xn ) · q = ∑ f j (x1 , . . . , xn ) · h−1 ( j) .
q∈M j∈[m]
In other words, for every monomial qx in the variables {x1 , . . . , xn } and monomial qz ∈ M, the coefficient
of the monomial qx qz in f˜ is simply the coefficient of the monomial qx in fh(qz ) . (For monomials qx , qz
such that qz 6∈ M, the coefficient of the monomial qx qz in f˜ is 0.)
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 170
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
For a = (a1 , . . . , an ) ∈ Fn , denote by f˜|a ∈ F[Z], the polynomial f˜ ∈ F[X, Z], after the substitution
x1 = a1 , . . . , xn = an .
Proposition 5.4. ∀a ∈ Fn , we have, f˜|a ∈ M, and H( f˜|a ) = f (a).
Proof. The proof is straightforward from the definitions. For every a = (a1 , . . . , an ) ∈ Fn ,
f˜|a (z1 , . . . , zn ) = f˜(a1 , . . . , an , z1 , . . . , zn ) = ∑ f j (a) · h−1 ( j) ∈ M .
j∈[m]
Thus,
H f˜|a = H ∑ j∈[m] f j (a) · h−1 ( j) = f1 (a), . . . , fm (a) = f (a) .
Proposition 5.5. If f = ( f1 , . . . , fm ) is poly(n)-definable (see Definition 1.3), then the polynomial f˜ ∈
F[X, Z] is poly(n)-definable.
Proof. Similar to the proof of Proposition 3.6.
5.4 The route to lower bounds
In this subsection, we prove our main results for polynomial-mappings f that elude polynomial-map-
pings Γ of degree 2. The results are given by four propositions and corollaries.
All four propositions and corollaries are only interesting for s < m (although this condition is not
stated explicitly). Recall that we think of all the parameters (r, s, m, etc.) as functions of the basic
parameter n.
Recall that given a polynomial mapping f : Fn → Fm , and given a field extension G ⊃ F, we can
think of f as a polynomial mapping f : Gn → Gm . This is because we assume that a polynomial mapping
f : Fn → Fm is given as a tuple ( f1 , . . . , fm ) of polynomials in F[x1 , . . . , xn ] ⊂ G[x1 , . . . , xn ] (see the
discussion in Subsection 1.4).
Proposition 5.6. For integers 3 ≤ r ≤ n ≤ s0 , and m = n+r−1 , and r0 = b2r/3c, let ΓG : Fs → Fm , where
r
0
s = O(s0 · n+rr0 −1 · r3 ), be the (homogenous) polynomial mapping of degree 2 from Proposition 5.3. Let
f : Fn → Fm be a polynomial mapping.
If over some field extension G ⊇ F,
Image( f : Gn → Gm ) 6⊂ Image(ΓG : Gs → Gm ) ,
then any arithmetic circuit (over F) for the polynomial f˜ : F2n → F (explicitly defined from f in Subsec-
tion 5.3), is of size > s0 .
Proof. Let us first prove the proposition for G = F.
By Proposition 5.3, for every g ∈ M, if there exists an arithmetic circuit of size s0 (over F) for the
polynomials g, then H(g) ∈ Image(ΓG ).
Assume for a contradiction that there exists an arithmetic circuit (over F) of size s0 , for the polyno-
mial f˜ : F2n → F. By substituting in this circuit x1 = a1 , . . . , xn = an , where a = (a1 , . . . , an ) ∈ Fn , we
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 171
R AN R AZ
obtain an arithmetic circuit of size s0 for the polynomial f˜|a , and note that by Proposition 5.4, f˜|a ∈ M.
Hence, by Proposition 5.3, (for every a1 , . . . , an ∈ F), H( f˜|a ) ∈ Image(ΓG ). Thus, by Proposition 5.4,
for every a1 , . . . , an ∈ F,
f (a1 , . . . , an ) = H( f˜|a ) ∈ Image(ΓG ) .
That is,
Image( f ) ⊂ Image(ΓG ) .
Assume now that G is a general field, extending F, and assume that
Image( f : Gn → Gm ) 6⊂ Image(ΓG : Gs → Gm ) .
By the part that we already proved (i. e., the case G = F), we know that any arithmetic circuit over G, for
the polynomial f˜, is of size > s0 . But any arithmetic circuit over F is in particular an arithmetic circuit
over G. Thus, any arithmetic circuit over F for the polynomial f˜ is of size > s0 . (Formally, we need to
verify that the polynomials f˜ and (ΓG )1 , . . . , (ΓG )m remain the same polynomials when we work over G,
rather than over F. This can be easily verified. For (ΓG )1 , . . . , (ΓG )m , it was noted after the definition of
ΓG that they do not depend on the field at all, but only on its characteristic. As for f˜, by its definition, its
coefficients are just corresponding coefficients from the polynomials f1 , . . . , fm , and hence they do not
depend on the field G.)
Corollary 5.7. Let 3 ≤ r ≤ n ≤ s, and m = n+r−1 be integers. Let r0 = b2r/3c. Let f : Fn → Fm be a
r
polynomial mapping. If over some field extension G ⊇ F, f is (s, 2)-elusive (see Definition 1.1), then any
arithmetic circuit (over F) for the polynomial f˜ : F2n → F (explicitly defined from f in Subsection 5.3),
is of size ≥ !
s
Ω n+r0 −1 .
r0 · r3
0
Proof. The proof follows immediately from Proposition 5.6. Let s0 = c · s/( n+rr0 −1 · r3 ), where c is a
small enough constant. If f is (s, 2)-elusive, then in particular it satisfies Image( f ) 6⊂ Image(ΓG ), where
ΓG is the mapping from Proposition 5.6.
Corollary 5.8. Let F be a field of characteristic not equal to 2. Let 3 ≤ r ≤ n ≤ s, and m = n+r−1
r be
0 n+r0 −1
integers. Let r = b2r/3c. Assume that s/ r0 ≥n ω(1) . If there exists a poly(n)-definable polynomial
n m
mapping f : F → F such that, over some field extension G ⊇ F, f is (s, 2)-elusive (see Definition 1.3
and Definition 1.1), then any arithmetic circuit for the permanent over F is of size ≥
!Ω(1)
s
n+r0 −1
.
r0 · r3
Proof. Assume that such a polynomial mapping f exists. By Proposition 5.5, and Corollary 5.7, the
polynomial f˜ : F2n → F (explicitly defined from f in Subsection 5.3) is poly(n)-definable, and any
arithmetic circuit (over F) for f˜ is of size ≥
!
s
Ω n+r0 −1 .
r0 · r3
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 172
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
Valiant proved that over any field of characteristic not equal to 2, the permanent is a complete
polynomial for the class VNP of poly(n)-definable polynomials [36] (see also [10, 6]). Hence, any
arithmetic circuit of size s0 for the permanent implies an arithmetic circuit of size poly(s0 ) for any other
poly(n)-definable polynomial. Hence, any arithmetic circuit for the permanent over F is of size
!Ω(1)
0 s
s ≥ n+r0 −1
.
r0 · r3
Corollary 5.9. Let 3 ≤ r ≤ n ≤ s, and m = n+r−1
r be integers (and recall that we think of r, s, m as
functions of n). Let r0 = b2r/3c. Assume that there exists a poly(s, m)-time Turing machine T such that:
• The inputs for T are r, n, s, m and a (homogenous) polynomial mapping Γ : Fs → Fm of degree 2,
given by all coefficients of the polynomials Γ1 , . . . , Γm (that are assumed to be in {0, 1}).
• The output of T is a poly(n)-definable polynomial mapping f : Fn → Fm (described, e. g., by an
arithmetic circuit for the polynomial g that defines it in Definition 1.3) such that, over some field
extension G ⊇ F,
Image( f : Gn → Gm ) 6⊂ Image(Γ : Gs → Gm ) .
Then, there exists a poly(s, m)-time Turing machine that on input n outputs a 2n-variables, poly(n)-
definable, polynomial f˜ (explicitly defined from f in Subsection 5.3, and described, e. g., by an arithmetic
circuit for the polynomial g that defines it in Definition 1.3), such that any arithmetic circuit for f˜ is of
size ≥ !
s
Ω n+r0 −1 .
· r 3
r 0
0
Proof. The proof follows immediately from Proposition 5.6. Let s0 = c · s/( n+rr0 −1 · r3 ), where c is
a small enough constant. We run the Turing machine T on the polynomial mapping Γ = ΓG , where
ΓG is the mapping from Proposition 5.6. Note that by Proposition 5.3, ΓG can be constructed in time
poly(s, m) (for details, see Proposition 5.3).
Acknowledgement
I am grateful to Zeev Dvir, Yael Tauman Kalai, Toni Pitassi, Omer Reingold, Amir Shpilka, Avi Wigder-
son and Amir Yehudayoff, for very helpful conversations and comments at different stages of this work.
References
[1] M ANINDRA AGRAWAL AND V. V INAY: Arithmetic circuits: A chasm at depth four. In Proc. 49th
FOCS, pp. 67–75. IEEE Comp. Soc., 2008. [doi:10.1109/FOCS.2008.32]. 144, 152
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 173
R AN R AZ
[2] M. A JTAI: Σ11 -formulae on finite structures. Ann. Pure Appl. Logic, 24:1–48, 1983.
[doi:10.1016/0168-0072(83)90038-6]. 138
[3] M ICHAEL A LEKHNOVICH , E LI B EN -S ASSON , A LEXANDER A. R AZBOROV, AND AVI
W IGDERSON: Pseudorandom generators in propositional proof complexity. SIAM
J. Comput., 34(1):67–88, 2004. A preliminary version appeared in FOCS 2000.
[doi:10.1137/S0097539701389944]. 144
[4] M ICHAEL A LEKHNOVICH AND A LEXANDER A. R AZBOROV: Lower bounds for the polynomial
calculus: Non-binomial case. Proc. Steklov Inst. Math., 242:18–35, 2003. A preliminary version
appeared in FOCS 2001. [doi:10.1109/SFCS.2001.959893]. 144
[5] WALTER BAUR AND VOLKER S TRASSEN: The complexity of partial derivatives. Theoret. Com-
put. Sci., 22(3):317–330, 1983. [doi:10.1016/0304-3975(83)90110-X]. 138, 143, 156, 160, 162,
167
[6] P ETER B ÜRGISSER: Completeness and Reduction in Algebraic Complexity Theory. Springer,
Berlin, 2000. 142, 163, 173
[7] P ETER B ÜRGISSER , M ICHEL C LAUSEN , AND M OHAMMAD A. S HOKROLLAHI: Algebraic Com-
plexity Theory. Springer, Berlin, 1997. 138
[8] DANNY D OLEV, C YNTHIA DWORK , N ICHOLAS P IPPENGER , AND AVI W IGDERSON: Super-
concentrators, generalizers and generalized connectors with limited depth. In Proc. 15th STOC,
pp. 42–51. ACM, 1983. [doi:10.1145/800061.808731]. 139
[9] M ERRICK L. F URST, JAMES B. S AXE , AND M ICHAEL S IPSER: Parity, circuits, and the
polynomial-time hierarchy. Theory Comput. Syst., 17(1):13–27, 1984. A preliminary version
appeared in FOCS 1981. [doi:10.1007/BF01744431]. 138
[10] J OACHIM VON ZUR G ATHEN: Feasible arithmetic computations: Valiant’s hypothesis. J. Symbolic
Comput., 4(2):137–172, 1987. [doi:10.1016/S0747-7171(87)80063-9]. 142, 163, 173
[11] J OACHIM VON ZUR G ATHEN: Algebraic complexity theory. Ann. Rev. Comput. Sci., 3:317–347,
1988. [doi:10.1146/annurev.cs.03.060188.001533]. 138
[12] 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, 1998. [doi:10.1145/276698.276872]. 138, 139
[13] D. G RIGORIEV AND A. R AZBOROV: Exponential lower bounds for depth 3 arithmetic circuits
in algebras of functions over finite fields. Appl. Algebra Engrg. Comm. Comput., 10(6):465–487,
2000. A preliminary version appeared in FOCS 1998. [doi:10.1007/s002009900021]. 138, 139
[14] J. H ÅSTAD: Almost optimal lower bounds for small depth circuits. Adv. Comput. Res., 5:143–170,
1989. A preliminary version appeared in STOC 1986. [doi:10.1145/12130.12132]. 138
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 174
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
[15] VALENTINE K ABANETS AND RUSSELL I MPAGLIAZZO: Derandomizing polynomial identity tests
means proving circuit lower bounds. Comput. Complexity, 13(1–2):1–46, 2004. A preliminary
version appeared in STOC 2003. [doi:10.1007/s00037-004-0182-6]. 144
[16] R ICHARD J. L IPTON: Polynomials with 0-1 coefficients that are hard to evaluate. SIAM J. Com-
put., 7(1):61–69, 1978. A preliminary version appeared in FOCS 1975. [doi:10.1137/0207004].
143
[17] S ATYANARAYANA V. L OKAM: Spectral methods for matrix rigidity with applications to size-
depth tradeoffs and communication complexity. J. Comput. System Sci., 63:449–473, 2001. A
preliminary version appeared in FOCS 1995. [doi:10.1006/jcss.2001.1786]. 141
[18] JACQUES M ORGENSTERN: How to compute fast a function and all its derivatives:
A variation on the theorem of Baur-Strassen. ACM SIGACT News, 16:60–62, 1985.
[doi:10.1145/382242.382836]. 143, 162, 167
[19] N OAM N ISAN: Lower bounds for non-commutative computation. In Proc. 13th STOC, pp. 410–
418. ACM, 1991. [doi:10.1145/103418.103462]. 138
[20] N OAM N ISAN AND AVI W IGDERSON: On the complexity of bilinear forms. In Proc. 27th STOC,
pp. 723–732. ACM, 1995. [doi:10.1145/225058.225290]. 141
[21] P. P UDL ÁK: Communication in bounded depth circuits. Combinatorica, 14:203–216, 1994.
[doi:10.1007/BF01215351]. 139
[22] PAVEL P UDL ÁK: A note on the use of determinant for proving lower bounds on the size of linear
circuits. Inform. Process. Lett., 74:197–201, 2000. [doi:10.1016/S0020-0190(00)00058-2]. 141
[23] R AN R AZ: On the complexity of matrix product. SIAM J. Comput., 32(5):1356–1369, 2003. A
preliminary version appeared in STOC 2002. [doi:10.1137/S0097539702402147]. 141
[24] R AN R AZ: Separation of multilinear circuit and formula size. Theory Comput., 2(6):121–135,
2006. A preliminary version appeared in FOCS 2004 with the title “Multilinear-NC1 6= Multilinear-
NC2 ”. [doi:10.4086/toc.2006.v002a006]. 138
[25] R AN R AZ: Multi-linear formulas for permanent and determinant are of super-polynomial size. J.
ACM, 56, 2009. A preliminary version appeared in STOC 2004. [doi:10.1145/1502793.1502797].
138
[26] R AN R AZ: Tensor-rank and lower bounds for arithmetic formulas. In Proc. 42nd STOC, pp. 659–
666. ACM, 2010. [doi:10.1145/1806689.1806780]. 144
[27] R AN R AZ AND A MIR S HPILKA: Lower bounds for matrix product in bounded depth circuits with
arbitrary gates. SIAM J. Comput., 32(2):488–513, 2003. A preliminary version appeared in STOC
2001. [doi:10.1137/S009753970138462X]. 139
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 175
R AN R AZ
[28] R AN R AZ AND A MIR Y EHUDAYOFF: Multilinear formulas, maximal-partition discrepancy and
mixed-sources extractors. J. Comput. System Sci., 2010. A preliminary version appeared in FOCS
2008. [doi:10.1016/j.jcss.2010.06.013]. 152
[29] A. A. R AZBOROV: Lower bounds on the size of bounded-depth networks over a complete basis
with logical addition (in Russian). Mat. Zametki, 41(4):598–607, 1987. An English translation
appeared in Mathematical Notes of the Academy of Sci. of the USSR 41(4) (1987) 333–338. 138
[30] A. A. R AZBOROV: Bounded arithmetic and lower bounds in Boolean complexity. In Feasible
Mathematics II, volume 13 of Progr. Comput. Sci. Appl. Logic, pp. 344–386. Birkhäuser, 1995.
144
[31] V ICTOR S HOUP AND ROMAN S MOLENSKY: Lower bounds for polynomial evaluation and
interpolation problems. In Proc. 32nd FOCS, pp. 378–383. IEEE Comp. Soc., 1991.
[doi:10.1109/SFCS.1991.185394]. 139, 144
[32] A. S HPILKA AND A. W IGDERSON: Depth-3 arithmetic circuits over fields of characteristic zero.
Comput. Complexity, 10(1):1–27, 2001. A preliminary version appeared in Conference on Com-
putational Complexity 1999. [doi:10.1007/PL00001609]. 139
[33] R. S MOLENSKY: Algebraic methods in the theory of lower bounds for Boolean circuit complexity.
In Proc. 19th STOC, pp. 77–82. ACM, 1987. [doi:10.1145/28395.28404]. 138
[34] VOLKER S TRASSEN: Polynomials with rational coefficients which are hard to compute. SIAM J.
Comput., 3(2):128–149, 1974. [doi:10.1137/0203010]. 143
[35] VOLKER S TRASSEN: Die Berechnungskomplexität der symbolischen Differentiation von Interpo-
lationspolynomen. Theoret. Comput. Sci., 1(1):21–25, 1975. [doi:10.1016/0304-3975(75)90010-
9]. 138
[36] L. G. VALIANT: Completeness classes in algebra. In Proc. 11th STOC, pp. 249–261, 1979.
[doi:10.1145/800135.804419]. 142, 163, 173
[37] L. G. VALIANT, S. S KYUM , S. B ERKOWITZ , AND C. R ACKOFF: Fast parallel com-
putation of polynomials using few processors. SIAM J. Comput., 12(4):641–644, 1983.
[doi:10.1137/0212043]. 140, 144, 152
[38] A NDREW C HI -C HIH YAO: Separating the polynomial-time hierarchy by oracles. In Proc. 26th
FOCS, pp. 1–10. IEEE Comp. Soc., 1985. [doi:10.1109/SFCS.1985.49]. 138
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 176
L OWER B OUNDS FOR A RITHMETIC C IRCUITS
AUTHOR
Ran Raz
professor
Department of Computer Science and Applied Mathematics
Weizmann Institute of Science
Rehovot 76100, Israel
ran.raz weizmann ac il
http://www.wisdom.weizmann.ac.il/∼ranraz/
ABOUT THE AUTHOR
R AN R AZ received his Ph. D. in 1992 from the Hebrew University under the supervision
of Michael Ben-Or and Avi Wigderson. Since 1994, he has been a faculty member in
the Faculty of Mathematics and Computer Science at the Weizmann Institute. His main
research area is complexity theory, with emphasis on proving lower bounds for com-
putational models. More specifically, he is interested in Boolean circuit complexity,
arithmetic circuit complexity, communication complexity, propositional proof theory,
probabilistically checkable proofs, quantum computation and communication, and ran-
domness and derandomization.
T HEORY OF C OMPUTING, Volume 6 (2010), pp. 135–177 177