Authors Neeraj Kayal, Chandan Saha, S{\'{e}}bastien Tavenas,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46
www.theoryofcomputing.org
On the Size of Homogeneous and of
Depth-Four Formulas with
Low Individual Degree
Neeraj Kayal∗ Chandan Saha† Sébastien Tavenas‡
Received August 18, 2016; Revised November 24, 2017; Published December 6, 2018
Abstract: Let r ≥ 1 be an integer. Let us call a polynomial f (x1 , x2 , . . . , xN ) ∈ F[x] a
multi-r-ic polynomial if the degree of f with respect to any variable is at most r. (This
generalizes the notion of multilinear polynomials.) We investigate the arithmetic circuits in
which the output is syntactically forced to be a multi-r-ic polynomial and refer to these as
multi-r-ic circuits. We prove lower bounds for several subclasses of such circuits, including
the following.
1. An N Ω(log N) lower bound against homogeneous multi-r-ic formulas (for an explicit
multi-r-ic polynomial on N variables).
√
1.1 Ω d/r
2. An (n/r ) lower bound against depth-four multi-r-ic circuits computing the
polynomial IMMn,d corresponding to the product of d matrices of size n × n each.
A conference version of this paper appeared in the Proceedings of the 48th Annual ACM Symposium on Theory of
Computing (STOC’16) [19].
∗ Supported by Microsoft Research India.
† Supported by Indian Institute of Science.
‡ Supported by CNRS, Université Savoie Mont Blanc.
ACM Classification: F.1.3, F.1.1
AMS Classification: 68Q17, 68Q15
Key words and phrases: complexity theory, lower bounds, algebraic complexity, arithmetic formulas,
arithmetic circuits, partial derivatives
© 2018 Neerak Kayal, Chandan Saha, and Sébastien Tavenas
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2018.v014a016
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
√
3. A 2Ω( N ) lower bound against depth-four multi-r-ic circuits computing an explicit
multi-r-ic polynomial on N variables.
1 Introduction
Arithmetic models of computation. An arithmetic circuit computes a polynomial function over some
underlying field F via a sequence of operations involving + and × starting from its inputs x1 , x2 , . . . , xN .
We typically allow arbitrary constants from F on the incoming edges to a + gate so that a + gate can
in fact compute an arbitrary F-linear combination of its inputs. The complexity of a circuit is measured
in terms of its size1 and depth.2 Being the most natural and intuitive way to compute polynomials,
arithmetic circuits have been widely investigated (see for example the book by Bürgisser, Clausen and
Shokrollahi [3] or the more recent surveys by Shpilka and Yehudayoff [32] and by Saptharishi [31] for
an overview of the problems and results in this area). A central open problem in this area is to prove
arithmetic circuit lower bounds (for some explicit family of polynomials). Progress on it has been made
in the form of lower bounds for some subclasses of circuits, one of the most significant ones being Raz’s
lower bound for multilinear3 formulas4 [28]. We study formulas that are a natural generalization of the
class of multilinear formulas. We now give some more motivation before giving a precise definition of
the relevant circuit subclasses studied and the lower bounds obtained here.
Background. Motivated by the question of whether computation can be efficiently parallelized, one
thread of work in this area [11, 36, 1, 29, 20, 34, 9] gives the loss in size incurred in transforming a
general circuit or formula into one of low depth (sometimes with additional structural restrictions on the
resulting low-depth circuits). In particular, these results say that proving sufficiently strong lower bounds
for (subclasses of) low-depth circuits implies lower bounds for arbitrary circuits as well. Low-depth
circuits being easier to analyze, this might be a potential pathway to general lower bounds. Somewhat
promisingly, a lot of new lower bounds have recently been proved for various subclasses of arithmetic
circuits, particularly for low-depth subclasses [12, 8, 13, 6, 4, 22, 14, 24, 17, 23, 21].
However, most of the present lower bounds can only handle subclasses of circuits having formal
degree which is rather low (equal to or sometimes slightly larger than the number of variables). To make
progress and remove the limitations of multilinearity and low formal degree, some recent work [18, 27]
looks at a model that generalizes multilinear circuits/formulas. Such a generalization also appears in the
hardness versus randomness trade-off result for bounded-depth circuits [5].
1 The size of a circuit is the number of edges in the circuit. This corresponds to the number of binary operations in the
computation.
2 The depth of a circuit is the maximum length of a path from an input to the output node. This corresponds to the amount of
parallelism afforded by the computation. The product-depth will correspond to the maximum number of product gates on a path
from an input to the output.
3 A polynomial f (x) ∈ F[x] is said to be multilinear if its degree with respect to any variable is at most 1. A circuit is said to
be (syntactically) multilinear if the polynomial computed at every node is syntactically forced to be multilinear—for details see
Definition 1.1 for the special case of r = 1.
4 Recall that a formula is a circuit in which the underlying graph is in fact a tree. It is more convenient to work with the
number of leaves of the tree as the size of the formula.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 2
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
The multi-r-ic circuit model. Intuitively, a multi-r-ic circuit is an arithmetic circuit in which the output
polynomial is syntactically constrained to have degree at most r with respect to any individual variable.
We now make this precise.
Definition 1.1. Define the formal degree of a node α with respect to a variable xi in an arithmetic circuit
inductively as follows. For a leaf α it is 1 if α is labelled with xi and zero otherwise; for an internal node
α labelled with × (labelled with +) it is the sum (the maximum, respectively) of the formal degrees of
the children with respect to xi ,
The formal degree of a circuit is the formal degree of its output node. We call an arithmetic circuit a
multi-r-ic circuit if the formal degree of the output node with respect to each variable is at most r.
The formal degree of a circuit represents what the degree of the output would have been if there
were no cancellations and is always an upper bound on the degree of the output. Note that the formal
(total) degree of a N-variate multi-r-ic circuit can be (r · N) which is asymptotically larger than N when
r = ω(1). In this work, we prove lower bounds for several subclasses of multi-r-ic circuits. Now, once
one has a lower bound for some explicit polynomial f (x) ∈ F[x] against a circuit subclass C, it is desirable
to try to make such an f come from as small a class D as possible.5 Following this general theme, we
have tried to minimize the complexity of our target polynomial f .
A polynomial is called homogeneous if all its monomials have the same total degree. A circuit is
called homogeneous if all its internal nodes compute a homogeneous polynomial.
Our results. Our lower bounds hold over any field unless mentioned otherwise explicitly. Our first
result is a superpolynomial lower bound for homogeneous multi-r-ic formulas.
Theorem 1.2. Homogeneous multi-r-ic formulas. Let r = r(N) be any integer. There exists an explicit
family of N-variate multi-r-ic polynomials PN,r such that any homogeneous multi-r-ic formula computing
2
PN,r must have a size of at least 2Ω(log (N)) . Moreover, if the field F contains r distinct r-th roots of
unity and has a size of at least (2Nr) then PN,r can be computed by a poly(Nr)-sized (nonhomogeneous)
depth-three multi-r-ic formula.
We probe a bit further in this direction and obtain improved lower bounds for homogeneous multi-r-ic
formulas of low depth.
Theorem 1.3 (Constant-depth homogeneous multi-r-ic formulas). Let r = r(N) be an integer and let p
be an integer. If
log N
p ≤ 0.9 (1.1)
log r + log log N
then there exists an explicit family of N-variate multi-r-ic polynomials PN,r such that any homogeneous
multi-r-ic formula of product-depth p computing PN,r must have a size of at least
1/p
Ω 1r ( N4 )
2 . (1.2)
5 This gives a separation between the classes C and D and enhances our understanding of the cost (in terms of size) that must
be incurred in order to transform a circuit in D to an equivalent one in C. It also enhances our understanding of the the proof
techniques involved.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 3
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
Moreover, if the field F contains r distinct r-th roots of unity and has a size of at least (2Nr) then PN,r can
be computed by a poly(Nr)-sized (nonhomogeneous) depth-three multi-r-ic formula.
Let us notice that, unlike Theorem 1.2, the previous bound degrades with the parameter r.
The proofs of these two results follow the strategy of first facilitating the analysis by reducing the
depth6 and then proving lower bounds against the resulting low-depth formula. As one hopes to be
able to implement some such strategy to obtain lower bounds against more powerful subclasses of
circuits (maybe even general arithmetic circuits), it makes sense to prove lower bounds against low-depth
multi-r-ic circuits (without the homogeneity restriction). Also, the “moreover” part of the above theorems
shows that nonhomogeneous depth-three multi-r-ic formulas are superpolynomially more powerful than
homogeneous multi-r-ic formulas of arbitrary depth. This further motivates our next few results on lower
bounds for low-depth multi-r-ic formulas without the homogeneity restriction. We represent a circuit of
depth p with a sequence of p alternating symbols (either Σ or Π) wherein the leftmost symbol denotes the
nature of the output gate. So for example, a ΣΠΣΠ circuit is a depth-four circuit where the output gate is
an addition gate. We denote by IMMn,d the (1, 1)-th entry of the product of d matrices of size n × n each.
Theorem 1.4 (Depth-four multi-r-ic formulas computing IMM). For any integer r = r(n) such that
any multi-r-ic ΣΠΣΠ circuit computing IMMn,d where d ≥ log2 n must have
r1.1 n and for any d r, √
d/r)
a size of at least7 (n/r1.1 )Ω( .
Moreover, one can notice that the reduction [35] of IMMn,d as a projection of Detn·d maintains the
multi-r-icity.
Corollary 1.5 (Depth-four multi-r-ic formulas computing determinant).√ For any integer r = r(n), any
1.1
multi-r-ic ΣΠΣΠ circuit computing Detn must have a size of at least 2Ω( n/r ) .
Note that the target polynomials, namely IMMn,d and Detn , in the above theorems are multilinear
polynomials. If we allow our target polynomial to be a multi-r-ic polynomial then we can obtain a lower
bound that does not degrade at all as r increases.
Theorem 1.6 (Depth-four multi-r-ic formulas computing a multi-r-ic polynomial). For any positive
integer r = r(N) there exists an explicit family {GN,r } of multi-r-ic N-variate
√
polynomials such that any
Ω( N )
multi-r-ic ΣΠΣΠ-circuit computing GN,r must have a size of at least 2 . Moreover, one can even
choose such a family GN,r so that it can in fact be computed by a poly(Nr)-sized multi-r-ic algebraic
branching program.
The three previous bounds hold for ΣΠΣΠ-circuits. Moreover, we can improve them in the case of
ΣΠΣ-circuits.
Theorem 1.7 (Depth-three multi-r-ic formulas computing IMM). For any integer r = r(n) such that
r n, any multi-r-ic ΣΠΣ-circuit computing IMMn,d has a size of at least (n/r)Ω(d) .
6 In this case, the depth reduction yields some sort of a depth-four formula with a specific, well-chosen structure—see
Lemma 4.2 for the details.
7 Through all the paper, the exponents 1.1 and 1.2 can in fact be chosen as close as we want to 1.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 4
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
Corollary 1.8 (Depth-three multi-r-ic formulas computing the determinant). For any integer r = r(n),
any multi-r-ic ΣΠΣ-circuit computing Detn has a size of at least 2Ω(n/r) .
Theorem 1.9 (Depth-three multi-r-ic formulas computing a multi-r-ic polynomial). For any positive
integer r = r(N) there exists an explicit family {GN,r } of multi-r-ic N-variate polynomials such that any
multi-r-ic ΣΠΣ-circuit computing GN,r must have a size of at least 2Ω(N) . Moreover, one can choose such
a family GN,r so that it can in fact be computed by a poly(Nr)-sized ΠΣΠ-circuit.
√One can notice that for any constant r the lower bound 2Ω(N) in Theorem 1.9 and the lower bound
2 N) in Theorem 1.6 are optimal since there is a depth-three circuit of size 2O(N) in the former case and
Ω(
a depth-four circuit in the latter case, computing the target polynomial.
Comparison to previous work. As mentioned earlier, most prior work failed to yield (superpolynomial)
lower bounds when the degree of the polynomial being computed and/or the formal degree of the circuit
was significantly larger than the number of variables.8 In this particular aspect, the above results represent
significant progress. For example, Theorem 1.2 and Theorem 1.6 yield (superpolynomial) lower bounds
against natural subclasses of circuits wherein the formal degree is allowed to be arbitrarily larger than
the number of variables. These results also yield improved lower bounds for some previously studied
subclasses.
1. Multilinear ΣΠΣΠ Circuits. While the focus of this work is on multi-r-ic formulas for r > 1 for
which lower bounds were previously not known, our results have interesting consequences for the
much more well-studied special case of r = 1 corresponding to multilinear formulas. Previously,
the best known9 lower bound against
√ multilinear-ΣΠΣΠ circuit computing any explicit N-variate
polynomial of degree d was 2Ω( d·log d) , where d N. Note√ that this does√ not increase with
10
N. The special case of Theorem 1.4 for r = 1 yields a n Ω( d) = (N/d) d) lower bound for
Ω(
multilinear-ΣΠΣΠ circuits computing IMMn,d .
2. Multi-r-ic ΣΠΣ-circuits. Multi-r-ic depth-three circuits were recently studied in [17] and a lower
r
bound of 2Ω(N/2 ) was obtained for an explicit multi-r-ic N-variate polynomial. In particular, no
superpolynomial lower bound seems to have been known when r = ω(log N). In comparison,
Theorem 1.9 gives an exponential lower bound which is independent of r.
8 Sometimes, as over finite fields [7], high formal degrees are allowed but these models can be “easily” transformed (and this
is how the proofs of these lower bounds work) into ones of low formal degrees. Notable exceptions could be found in other
recent works trying to break this barrier [16, 23, 25].
9 Actually a lot of the work on multilinear formulas deal with polynomials such as the determinant and the permanent where
the number of variables N is a fixed function of d, e. g., N = d 2 in the case of the permanent and the determinant. Therefore the
statements of the results themselves do not reveal the structure of the lower bound as a function of both N and d. It seems that
the proof technique employed in Raz [28] and Raz-Yehudayoff [30] only yields a lower bound that is independent of N for when
N is much larger than d (in a multilinear polynomial N cannot be smaller than d), a key initial step in their argument involving
random restrictions kills off the extra variables so that the number of surviving variables is comparable to the degree and then
works with this restricted polynomial. √
10 The work of [6] looks at multilinear-ΣΠΣΠ-circuits with the additional restriction of homogeneity and obtains a nΩ( d)
lower bound for IMMn,d .
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 5
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
Moreover, Theorem 1.2 and Theorem 1.3 are a generalization (from r = 1 to arbitrary values of r)
of the work of [10] and follows the same overall proof strategy. The main difference appears at the
step of monomials counting. They directly bound the number of monomials which appear in the
formula whereas we bound the number of occurrences of a particular subset of these monomials.
2 Proof overview
In this section we give an overview of the proof of some of these lower bounds with an emphasis on those
ingredients of the proof that are new here as compared to prior work in the area.
Homogeneous multi-r-ic formulas. Our proof is a generalization (from r = 1 to arbitrary values of
r) of the work of [10] and follows the same overall proof strategy of first doing a depth reduction11 in
order to make the resulting expression easier to analyze and then proving lower bounds on the size of
such expressions. Roughly, if f is any N-variate polynomial computed by a multi-r-ic formula Φ of size
s then f can be written as
f = T1 + T2 + · · · + Ts , (2.1)
where each Ti is a multi-r-ic polynomial that can be expressed as a product of (log N)-many homogeneous
polynomials
√
Ti = Qi1 · Qi2 · · · · · Qi log N where each Qi j has at least N-many fresh variables (2.2)
(see Lemma 4.2 and the preceding discussion for the precise definitions and statements12 ). Moreover, if
the formula Φ is also homogeneous then each Qi j is homogeneous as well. We then carefully choose
a subset of multi-r-ic monomials13 which we refer to as extremal monomials (see Definition 4.5 for
the precise statement) and employ a result from extremal combinatorics called Sperner’s theorem to
upper bound the number of extremal monomials in a homogeneous multi-r-ic term T of the form given
by Equation (2.2). We then choose our target polynomial f to have the maximum possible number of
extremal monomials (and also to be easily computed by a nonhomogeneous multi-r-ic depth-three circuit).
Finally looking at the ratio of the number of extremal monomials in f to that in T yields the stated lower
bound.
Depth-Four Circuits. The proof for multi-r-ic depth-four circuits builds on some of the recent work [14,
24] on homogeneous depth-four circuits and shares many ingredients with these. Let f be a polynomial
computed by a small multi-r-ic depth-four circuit. We first employ random restrictions to reduce the
11 A similar depth reduction is also given in the exposition of Raz’s proof in [32].
12 For comparison, we mention that in the special case of r = 1, the Q
i j can be ensured to have disjoint sets of variables. It
seems unlikely that such a decomposition with the Qi j being variable disjoint can be obtained for arbitrary r.
13 For comparison, we mention that [10] observe that the ratio of the maximum possible number of monomials in a homoge-
N
neous multilinear polynomial (a N-variate homogeneous multilinear polynomial contains at most N/2 -many monomials) to the
number of monomials in a term T of the form given by Equation (2.2) is superpolynomial and this essentially yields the lower
bound. It seems quite implausible that this ratio of naive monomial counts will yield meaningful lower bounds when r is large.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 6
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
support size14 of the monomials appearing in our depth-four circuit. We then get a representation of the
following form:
f (x) = T1 + T2 + · · · + Ts , (2.3)
where each term Ti is a multi-r-ic polynomial of the form Ti = Qi1 · Qi2 · · · · · QiD , every monomial
in each Qi j has a relatively small number of variables. Since each Ti is multi-r-ic, the number D of
factors in it can at most be (N · r) and in general this upper bound is tight. Now such representations
did occur at the intermediate stages in some recent pieces of work [14, 24] and a complexity measure
called dimension of projected shifted partials was devised to analyze these. It involves looking at all
the low-order partial derivatives of f , multiplying these with monomials of a suitable degree, applying
a carefully chosen linear operator π : F[x] 7→ F[x] and looking at the dimension of the resulting set
of polynomials. It turns out that when the number of factors D significantly exceeds the number of
variables N the bounds on the dimension of shifted partials that were proved in earlier works do not
seem to yield any nontrivial lower bound overall. The key observation here is that one can get around
this difficulty using a complexity measure that is some sort of a hybrid of the shifted partials measure
with what is used in the work of [28, 30]. Specifically, we partition our set of variables x into two sets
x = y ] z where the size of y is significantly larger compared to the size of z.15 We observe that if instead
of taking all the (low order) derivatives, we take the (low order) derivatives with respect to only the
y-variables and subsequently set them to zero then effectively the number of factors becomes more like
|z| · r which is much smaller than (|x| · r) = (N · r) while still giving us a large enough space of partial
derivatives to work with. In order to highlight this idea and illustrate its power in a simpler situation, in
Theorem 6.4 we first show how this can be used to obtain a (N/r3 )Ω(d) lower bound against multi-r-ic
depth-three circuits computing an explicit multilinear polynomial of degree d on N = Θ(d 3 ) variables (by
considering fd,d/3 in Theorem 6.4). We then show how some of the other ingredients from some recent
lower bound proofs [12, 8], combined with some judicious bounds √ on the dimension of some relevant
sets of polynomials (Lemma 7.4) can be used to obtain a 2Ω( N) lower bound for multi-r-ic depth-four
circuits computing an explicit polynomial (Theorem 1.6). This lower bound degrades with r in case the
target polynomial is multilinear (Theorem 1.4).
3 Preliminaries
3.1 Notation
[n] shall denote the set of first n positive integers, i. e., [n] = {1, 2, . . . , n}. For any finite set A and any
integer k ≤ |A|, Ak shall denote the set of all subsets of A of size exactly k. We will often use boldfaced
letters for tuples of variables or numbers. For example x will usually denote an N-tuple of variables
(x1 , x2 , . . . , xN ) while r = (r1 , r2 , . . . , rN ) will usually denote an N-tuple of non-negative integers (the
dimension N will usually be clear from context).
14 The support size of a monomial is the number of distinct variables appearing in it, i. e., if m = xe1 · xe2 · · · · · xeN is a monomial
1 2 N
then the support size of m, denoted by |Supp(m)| is the size of the set {i : ei ≥ 1} ⊆ [N].
15 For comparison, [28, 30] also partition the variables into two sets but it is crucial to their argument that the two sets have
nearly the same size and that the partition is chosen randomly. In contrast, we choose the partition deterministically and it is
crucial to our argument that the two parts have rather unequal sizes.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 7
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
Some numerical estimates. We will employ the following well-known numerical estimates:
Proposition 3.1.
1. Binomial Estimates.
n k
n en k
≤ ≤ and
k k k
22n 22n
2n
√ ≤ ≤√ (given by Stirling’s formula).
2 n n 2n
2. Exponential Estimates.
ex ≥ 1 + x for all x ∈ R, and
x
e ≤ 1 + 2x for x ∈ [0, 1].
Let x = (x1 , x2 , . . . , xN ) be an N-tuple of formal variables. We work with the ring of polynomials F[x]
over some underlying field F. We will use the following notation related to (sets) of polynomials and
maps between them.
Sets of polynomials. For a subset of variables z ⊂ x, we will denote by z=` the set of all monomials in
the z variables of degree exactly `. Thus if z = (z1 , z2 , . . . , zm ) then
def
z=` = {zi11 · z2i2 · · · · · zimm : (i1 , i2 , . . . , im ) ∈ Zm
≥0 , i1 + i2 + · · · + im = `}. (3.1)
Similarly, z≤` shall denote the set of all monomials over the z-variables of degree at most `. Let y ⊆ x be
a subset of variables of x. ∂ =k
y f shall denote the set of all k-th order partial derivatives of f with respect
to the y variables, i. e.,
∂k f
def
∂ =k
y f = : i1 , i2 , . . . , ik ∈ [|y|] . (3.2)
∂ yi1 · ∂ yi2 · · · · · ∂ yik
For two sets of polynomials A, B ⊆ F[x], the set A · B shall be the set of pairwise products, i. e.,
def
A · B = { f (x) · g(x) : f (x) ∈ A, g(x) ∈ B}. (3.3)
For a set of polynomials A ⊆ F[x], the dimension of A will denote the dimension of the F-vector space
generated by A.
Degree with respect to a subset of variables. Let f (x) ∈ F[x] be a polynomial and z ⊆ x be a subset
of variables. The z-degree of f , denoted by degz ( f ), is the degree of f when viewed as a polynomial
over the z-variables with coefficients from the function field F(y), where y = x \ z.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 8
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
Support and z-support. Let z ⊆ x be a subset of variables and m = x1e1 · x2e2 · · · · · xNeN in F[x] be a
monomial. The support of m, denoted by Supp(m), is the subset of variables appearing in it. The
z-support of m, denoted by Suppz (m)), is the subset of z-variables appearing in it. Formally,
def def
Supp(m) = {i : ei ≥ 1} ⊆ [N], Suppz (m) = {i : xi ∈ z and ei ≥ 1} ⊆ [N]. (3.4)
Isomorphic polynomials. We will say that two N-variate polynomials f (x), g(x) ∈ F[x1 , x2 , . . . , xN ]
are isomorphic if one can be obtained from the other via a renaming of the variables, i. e., there exists a
permutation π ∈ SN such that
f (x1 , x2 , . . . , xN ) = g(xπ(1) , xπ(2) , . . . , xπ(N) ). (3.5)
Linear maps and homomorphisms. We will sometimes need to take a subset y ⊆ x of variables from
x and set them to zero in some relevant collection of polynomials. We employ the following notation in
this regard. For a subset y ⊆ x, σy : F[x] 7→ F[x] shall denote the homomorphism corresponding to setting
the variables in y to zero. It is formally defined as16 :
(
0 if xi ∈ y,
σy (xi ) = (3.6)
xi otherwise.
For any set of polynomials S ⊆ F[x] and any (linear) map σ : F[x] 7→ F[x], σ (S) shall denote the set
of polynomials obtained by applying σ to every polynomial in S, i. e.,
def
σ (S) = {σ ( f ) : f ∈ S}. (3.7)
The Iterated Matrix Multiplication. Let n, d ≥ 2 be two parameters. We consider polynomials defined
on variable sets x1 , . . . , xd . For i ∈ [d] \ {1, d}, let xi be the set of variables xi, j,k for j, k ∈ [n]; for i = 1,
let x1 be the set of variables x1,1, j and for i = d, let xd be the set of variables xd, j,1 where j ∈ [n]. Let
S
x = i∈[d] xi .
The Iterated Matrix Multiplication polynomial on x, denoted by IMMn,d , is defined to be
IMMn,d = ∑ x1,1, j1 · x2, j1 , j2 · x3, j2 , j3 · · · · · xd−1, jd−2 , jd−1 · xd, jd−1 ,1 . (3.8)
j1 ,..., jd−1
Note that the polynomial IMMn,d is the value of the product of d matrices M1 , M2 , . . . , Md (of dimensions
1 × n, n × n (d − 2 times), and n × 1).
3.2 Multi-r-ic models
Let Φ be an arithmetic formula. Φ b ∈ F[x] will denote the output polynomial computed by Φ while
Size(Φ) will denote the size (the number of leaves) of Φ. If α is a node of Φ, we will denote by Φα the
sub-formula rooted at α. In analyzing formulas in which the formal degree of every variable is bounded,
it is naturally convenient to keep track of the degree of each variable in the polynomials computed at
intermediate nodes of the formula. We will employ the following notation for this purpose.
16 This map then extends via F-linearity and multiplicativity to all of F[x].
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 9
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
Definition 3.2. Let r = (r1 , r2 , . . . , rN ) be an N-tuple of nonnegative integers.
1. Support of r. The support of r is the set of indices of the non-zero coordinates. More formally,
def
Supp(r) = {i ∈ [N] | ri 6= 0}. (3.9)
2. Multi-r-ic polynomials. We say a polynomial f (x) is a multi-r-ic polynomial if degxi ( f ) ≤ ri for
all i ∈ [N].
3. Multi-r-ic formulas. We say an arithmetic formula Φ is a multi-r-ic formula if for all i ∈ [N], the
formal degree of Φ with respect to the variable xi is at most ri .
For conciseness, a multi-(r, r, . . . , r)-ic polynomial17 (resp. formula) will be referred (as defined
before) to simply as a multi-r-ic polynomial (resp. formula). In particular, multi-1-ic polynomials are
exactly multilinear polynomials and multi-1-ic formulas are syntactically multilinear formulas. This
notational device will aid us in analyzing formulas via the labelling of every node α with an N-tuple that
upper bounds the syntactic degree of the polynomial computed at α with respect to the various formal
variables. We refer to such labelled formulas as certified multi-r-ic formulas and the precise properties
that such labellings satisfy are captured in the definition below.
Definition 3.3 (Certified multi-r-ic formulas). Let r = (r1 , r2 , . . . , rN ) be an N-tuple of nonnegative
integers. A certified multi-r-ic formula is an arithmetic formula such that each gate α is labelled by an
N-tuple dα = (d1 , . . . , dN ) of non-negative integers such that
• the output is labelled by r,
• if α is the input variable xi , then di ≥ 1,
• if α is an addition gate with children β1 , β2 , . . . , β p , then dα = dβ1 = dβ2 = . . . = dβ p ,
• and if α is a multiplication gate of children β1 , β2 , . . . , β p then18
dα = dβ1 + dβ2 + · · · + dβ p .
It is readily verified that a natural top-down labelling procedure provides such a labelling to any
multi-r-ic formula.
Proposition 3.4. Let r = (r1 , r2 , . . . , rN ) be an N-tuple of nonnegative integers. If Φ is a certified multi-r-
ic formula, then the formal degree of Φ with respect to the variable xi is at most ri . Conversely, if Φ is a
multi-r-ic arithmetic formula, then there exists a labelling of the vertices such that the labelled formula is
certified multi-r-ic.
17 Here, r is any positive integer.
18 Here “+” naturally denotes component-wise addition of N-tuples.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 10
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
Proof. The forward direction is immediate by definitions. Now consider the other direction. We will
assign a labelling so that if a gate α is labelled by d = (d1 , d2 , . . . , dN ), then the formal degree of α with
respect to xi is at most di . Let us show it by descending induction on Φ. If α is the output, we label it by
r. By assumption we have that the degree with respect to each variable xi is bounded by ri . If α is an
addition gate labelled by dα such that its children are not labelled, we label all the children by dα . As
the formal degrees of the children are bounded by the degree of α, the condition is satisfied. Otherwise
α is a multiplication gate labelled by dα = (d1 , d2 , . . . , dN ) having non-labelled children β1 , . . . , β p . For
i ∈ [N] and j ∈ [p], let the formal degree of β j with respect to xi be e ji . Then the formal degree of α with
respect to xi equals e1i + · · · + e pi and is upper bounded by di . Then for all j ≥ 2 we assign the label
def
dβ j = (e j1 , e j2 , . . . , e jN ) (3.10)
to the child β j and
def
dβ1 = dα − dβ2 − dβ3 − · · · − dβ p (3.11)
to the first child β1 . Thus the sum of the dβ j equalsdα and it is easy to check that the i-th coordinate of
dβ j is an upper bound for the formal degree of β j with respect to xi (for all j ∈ [p] and i ∈ [N]).
4 Homogeneous multi-r-ic formulas
In this section we implement the strategy outlined in section 2 to obtain superpolynomial lower bounds
for homogeneous multi-r-ic formulas.
4.1 Log-product decomposition
In this section we show that if a multi-r-ic polynomial f (x) is computed by a multi-r-ic formula Φ of size
s then f can be written as a sum of s polynomials having a rather special structure that we will exploit.
We first capture the structure of the summands in the following definition.
Definition 4.1. Let d = (d1 , . . . , dN ) be an N-tuple of nonnegative integers and T (x) ∈ F[x] be a poly-
nomial on N variables. Let v, L ≥ 0 be integers. We will say that T has a (d, v, L)-form if there exist v
pairs
(g1 (x), d1 ), (g2 (x), d2 ), . . . , (gv (x), dv ), (4.1)
where each d j ∈ ZN≥0 is an N-tuple and each g j (x) is a multi-d j -ic homogeneous polynomial such that:
1. T (x) is a multi-d-ic polynomial,
2. T (x) = g1 (x) · g2 (x) · · · · · gv (x),
3. d = d1 + d2 + · · · + dv ,
4. for all i ∈ [v] we have Supp(di ) \ ≥ L.
S
1≤ j<i Supp(d j )
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 11
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
Intuitively, the first three conditions specify that T is a multi-d-ic polynomial that is a length-v product
of multi-di -ic polynomials. The fourth condition intuitively says that each factor gi contains at least L
fresh variables, i. e., variables which do not occur in the previous g j ’s. factors g j .
Lemma 4.2. Let v ≥ 1 be an integer, d = (d1 , . . . , dN ) be an N-tuple of non-negative integers and f√be a
N-variate polynomial computed by a homogeneous
√ multi-d-ic formula of size s. If |Supp(d)| ≥ 3v−1 d Ne,
then there exist s homogeneous (d, v, d Ne)-form polynomials T1 , T2 , . . . , Ts such that f = T1 + T2 + · · · +
Ts .
We will need a suitable adaptation of an observation that is common to many depth-reduction results
for arithmetic (and even Boolean) formulas.
Proposition 4.3. Let f (x) be a polynomial computed by a certified multi-d-ic formula Φ and let α be
any node in Φ having a label dα . Then there exist certified formulas Ψ and Λ such that
Φ b ·Φ
b =Ψ bα + Λ
b (4.2)
where
1. Λ is a certified multi-d-ic formula, Ψ is a certified multi-(d − dα )-ic formula, and
2. Size(Φα ) + Size(Λ) ≤ Size(Φ).
3. If Φ is homogeneous then Ψ, Λ are also homogeneous formulas.
4. If Φ is of product-depth p then Ψ, Λ are of product-depth at most p.
Proof. Let β0 = α, β1 , β2 , . . . , βt be the sequence of nodes in the (unique) path from α to the root node of
Φ. So β1 is the parent of α, β2 is the grandparent of α and so on and βt is the root node of Φ. It suffices
to prove (via induction) that for every i ≥ 0
Φ bi ·Φ
bβ = Ψ bα + Λ
bi (4.3)
i
where
1. Λi is a certified multi-dβi -ic formula and Ψi is a certified multi-(dβi − dα )-ic formula, and
2. Size(Φα ) + Size(Λi ) ≤ Size(Φβi ).
The base case i = 0. This is easy to verify.
The inductive step. Let βi+1 have children βi and γ1 , . . . , γq with labels dβi and dγ1 , . . . , dγq , respectively.
There are two cases. The node βi+1 is a + node. Then by definition we have dβi+1 = dβi = dγ1 = · · · = dγq .
Now define
def def
Ψi+1 = Ψi , Λi+1 = Λi + Φγ1 + · · · + Φγq . (4.4)
Then Λi+1 is a certified multi-dβi+1 -ic formula and Ψi+1 is a certified multi-(dβi+1 − dα )-ic formula. The
other case of the inductive step is where βi+1 is a × gate. Then by definition we have
dβi+1 = dβi + dγ1 + · · · + dγq .
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 12
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
Now define
def def
Ψi+1 = Ψi × Φγ1 × · · · × Φγq , Λi+1 = Λi × Φγ1 × · · · × Φγq , (4.5)
with the natural labelling to the root nodes of Ψi+1 and of Λi+1 that this definition entails. Then Λi+1 is
computed by a certified multi-dβi+1 -ic formula while Ψi+1 is computed by a certified multi-e-ic formula,
where
e = (dβi − dα ) + dγ1 + · · · + dγq = dβi+1 − dα . (4.6)
Finally note that in the two cases we have:
Size(Φβi+1 ) ≥ Size(Φβi ) + Size(Φγ1 ) + · · · + Size(Φγq )
≥ (Size(Φα ) + Size(Λi )) + Size(Φγ1 ) + · · · + Size(Φγq )
(by inductive hypothesis)
= Size(Φα ) + (Size(Λi ) + Size(Φγ1 ) + · · · + Size(Φγq )
= Size(Φα ) + Size(Λi+1 ).
This completes the proof of the inductive step. The last two properties of Ψ, Λ are also easily checked
from their definitions. This completes the proof of the proposition.
Here we see how to use it to get the desired depth reduction.
Proof of Lemma 4.2. By Proposition 3.4 we can assume that the formula Φ is in fact a certified multi-d-ic
homogeneous formula. We can also assume without loss of generality19 that every node in the formulas
has fanin20 at most 2. We prove the result by induction on v and s.
√
Induction basis. If v = 1, then f is already in (d, 1, d Ne)-form.
If s = 1, the formula is just a leaf node and
√ f depends√ on at most one variable—say xi . Now since
the support of d is large (at least 3v−1 · d Ne ≥ v · d Ne) we can decompose d as
d = d1 + d2 + · · · + dv−1 + dv
such that:
1. i ∈ Supp(d1 ),
√
2. |Supp(d1 )| = |Supp(d2 )| = · · · = |Supp(dv−1 )| = d Ne,
3. Supp(di ) ∩ Supp(d j ) = 0/ for any 1 ≤ i < j ≤ v.
√
Then, it is easy to check that f is in (d, v, d Ne)-form via the pairs
( f , d1 ), (1, d2 ), . . . , (1, dv ). (4.7)
That concludes this case.
19 Since we use the number of leaves of a formula as a measure of its size.
20 The fanin of a node is the number of inputs to a node.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 13
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
Induction step. Let us prove the lemma for a fixed value of (v, s) with v ≥ 2. By hypothesis, f is
computed by a homogeneous certified multi-d-ic formula Φ. There are two cases.
• If one leaf α of Φ is such that |Supp(dα )| ≥ |Supp(d)|/3 where dα is the label of the node α.
By Proposition 4.3 we have Φ b =Ψ b ·Φbα + Λ b where Λ is a multi-d-ic formula of size at most
√
s − 1. Using the inductive hypothesis, it suffices to show that (Ψ
b ·Φ
b α ) is in (d, v, d Ne)-form.
To see this first note that since α is a leaf node so Φ
b α depends on at most one variable—say
√ √
xa . Now since the support of dα is large (at least 3v−2 · d Ne ≥ (v − 1) · d Ne) we can
decompose dα as
dα = d1 + d2 + · · · + dv−1 + dv
such that:
1. a ∈ Supp(d1 ),
√
2. |Supp(d1 )| = |Supp(d2 )| = · · · = |Supp(dv−1 )| = d Ne,
3. Supp(di ) ∩ Supp(d j ) = 0/ for any 1 ≤ i < j ≤ v.
Notice that dv has no restriction about the size of its support and it just contains the remainder
of the support.
Also we have
[
Supp(d − (d1 + d2 + · · · + dv−1 )) \ Supp(d j )
j<v
= |Supp(d)| − ∑ Supp(d j )
j<v
v−1
√ √ √
≥3 · d Ne − (v − 1) · d Ne ≥ d Ne. (4.8)
√
With the above facts in hand, it is easy to check that (Ψ b ·Φ
b α ) is in (d, v, d Ne)-form via the
pairs
(Φ b d − (d1 + d2 + · · · + dv−1 )).
b α , d1 ), (1, d2 ), (1, d3 ), . . . , (1, dv−1 ), (Ψ,
That concludes this case.
• Otherwise all the leaves have support smaller than |Supp(d)|/3. As the fan-in of every gate is
bounded by 2, there exists a node α in Φ with label dα such that
1 2
|Supp(d)| ≤ |Supp(dα )| ≤ · |Supp(d)| . (4.9)
3 3
By Proposition 4.3, there exist certified formulas Ψ and Λ such that
Φ bα · Ψ
b =Φ b + Λ,
b (4.10)
where size of Φα and of Λ is at most (s − 1) each. So we apply the induction hypothesis on
Φα and Λ. Now Λ is a certified multi-d-ic formula so by induction hypothesis
b = T10 (x) + · · · + Ts0 (x)
Λ (4.11)
1
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 14
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
√
where each Ti0 has a (d, v, d Ne)-form and s1 ≤ Size(Λ). Now Ψ
b is a homogeneous multi-
(d − dα )-ic polynomial. Moreover,
1 √
|Supp(dα )| ≥ |Supp(d)| ≥ 3v−2 · d Ne. (4.12)
3
By the induction hypothesis,
b α = T1 (x) + · · · + Ts (x),
Φ (4.13)
2
√
where each Ti has a (dα , v − 1, d Ne)-form and s2 ≤ Size(Φα ). Thus,
! !
s2 s1
f = ∑ Ti · Ψ b + ∑ T0 . (4.14)
i
i=1 i=1
Since
s1 + s2 ≤ Size(Λ) + Size(Φα )
≤ Size(Φ)
√
it suffices to show that for all
√ i the polynomials (Ti · b have a (d, v, d Ne)-form. Since each
Ψ)
Ti is already in (dα , v − 1, d Ne)-form and Ψ b is a multi-(d − dα )-ic polynomial, it suffices
√
to verify that |Supp(d − dα ) \ Supp(dα )| ≥ d Ne. Now
|Supp(d − dα ) \ Supp(dα )| = |Supp(d)| − |Supp(dα )|
2
≥ |Supp(d)| − · |Supp(d)|
3
1 v−1 √
≥ · 3 · d Ne
3√
≥ d Ne (as v ≥ 2). (4.15)
This completes the inductive step and hence proves the lemma.
Corollary 4.4. Let r ≥ 1 be an integer and let r = (r, r, . . . , r). If a N-variate polynomial f is computed
by a homogeneous multi-r-ic formula of size s then there exist s homogeneous multi-r-ic polynomials
T1 , T2 , . . . , Ts such that
s √
f = ∑ Ti where each Ti has a homogeneous (r, blog(N)/4c, d Ne)-form. (4.16)
i=1
Proof. We can directly apply Lemma 4.2 for v = blog(N)/4c. It is possible since
log(N) √
|Supp(r)| = N ≥ 3 4 −1 · d Ne . (4.17)
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 15
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
4.2 Counting extremal monomials
From the log-product decomposition described in the previous section, our problem boils down to
understanding the sums of (d, v, L)-forms. Our next definition will help us describe the weakness of such
summands that is being exploited here.
Definition 4.5 (Extremal monomials). Let d = (d1 , d2 , . . . , dN ) ∈ ZN≥0 be an N-tuple and m ∈ F[x] be
a multi-d-ic monomial on N variables. We will call m as a d-extremal monomial if the degree of m
with respect to any variable x j is either the minimum possible or the maximum possible amount, i. e.,
degx j (m) ∈ {0, d j } for all j ∈ [N].
In this subsection, we will show that a term of our log-product decomposition (Corollary 4.4) has a
relatively small number of extremal monomials. Specifically,
Lemma 4.6 (Upper bound on the number of extremal monomials in a term). Let T (x) be an N-variate
polynomial and d ∈ ZN≥0 be an N-tuple of non-negative integers. If T is homogeneous and has a
(d, v, L)-form then the number of d-extremal monomials in T is at most 2N /Lv/2 .
The rest of this subsection is devoted to a proof of this lemma. We will need the following result from
extremal combinatorics due to Sperner [33] (a proof of this can be found in the book [2]).
In the following, 2A will denote the set of all subsets of A.
Theorem 4.7 (Sperner’s Theorem). Let N be an integer and F ⊆ 2[N] be a set of subsets of [N]. Such an
F is called an antichain if and only if for all distinct I and J in F we have I 6⊆ J and J 6⊆ I. If F ⊆ 2[N] is
an antichain then
N
|F| ≤ . (4.18)
N/2
We use it to first bound the number of extremal monomials in any homogeneous polynomial.
def
Lemma 4.8. Let d ∈ ZN≥0 be an N-tuple and g(x) ∈ F[x] be a multi-d-ic polynomial. Let N1 = |Supp(d)|.
If g is homogeneous then the number of d-extremal monomials in g is at most
2N1
N1
≤√ . (4.19)
N1 /2 N1
Proof of Lemma 4.8. Let d = (d1 , d2 , . . . , dN ). We can first assume that di > 0 and that degxi (g) = di for
all i ∈ [N] (otherwise the corresponding variable xi does not appear in any d-extremal monomial in g and
we can effectively remove this variable from consideration). Now looking at the support of the extremal
monomials in g gives us a collection of subsets of [N]. Specifically, for any d-extremal monomial m let:
def
Sm = {i ∈ [N] : degxi (m) = di } ⊆ [N]. (4.20)
Let us consider the set
def
Ig = {Sm : m is d-extremal} ⊆ 2[N] . (4.21)
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 16
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
Via Sperner’s theorem (Theorem 4.7), it is sufficient to prove that Ig is an antichain. If it is not the case, it
means that there exist d-extremal monomials m1 and m2 in g such that Sm1 is a proper subset of Sm2 . In
particular,
def
deg(m2 ) = ∑ di = ∑ di + ∑ d j > deg(m1 ) (since every d j > 0). (4.22)
i∈Sm2 i∈Sm1 j∈(Sm2 \Sm1 )
This contradicts the premise that g is homogeneous.
The final inequality is given by Proposition 3.1.
Lemma 4.9. Let d1 , d2 , . . . , dv ∈ ZN≥0 be N-tuples and g1 (x), g2 (x), . . . , gv (x) ∈ F[x] be N-variate poly-
nomials such that the i-th polynomial gi (x) (with i ∈ [v]) is multi-di -ic. Let
def
d = d1 + d2 + · · · + dv and T = g1 · g2 · · · · · gv . (4.23)
Let !
def [
Ni = Supp(di ) \ Supp(d j ) . (4.24)
j<i
If all the gi are homogeneous polynomials then the number of d-extremal monomials in T is at most
2N1 +N2 +···+Nv
√ . (4.25)
N1 · N2 · · · · Nv
Proof. We prove it by induction on v. We can first assume without loss of generality that Supp(d) = [N]
(otherwise for any i ∈ [N] \ Supp(d) the corresponding variable xi does not appear in any monomial in T
and we can effectively remove this variable from consideration). If v = 1, the result is directly given by
Lemma 4.8. Now consider the case T = g1 · g2 · · · · · gv · gv+1 . Let
g = g1 · g2 · · · · · gv and e = d1 + d2 + · · · + dv = (e1 , . . . , eN ) (4.26)
so that
T = g · gv+1 and d = e + dv+1 .
Now note that a d-extremal monomial in T is a monomial from
{e-extremal monomials in g} · {dv+1 -extremal monomials in gv+1 }. (4.27)
Claim 4.10. If m1 is an e-extremal monomial in g, the number of monomials m2 from gv+1 such that
(m1 · m2 ) is d-extremal in T is at most
2Nv+1
√ . (4.28)
Nv+1
Let us first assume that the claim is true. In this case, by induction hypothesis the number of e-extremal
monomials in g is at most
2N1 +···+Nv
√ (4.29)
N1 · · · · · Nv
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 17
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
which implies the result. Let us prove the claim. Fix any e-extremal monomial m1 . Now there is a natural
partition induced on the set of variables as follows:
def def
Y = Supp(e) and Z = (Supp(dv+1 ) \ Supp(e)) = [N] \Y. (4.30)
Fix an e-extremal monomial m1 in g. We observe that there is a one-one correspondence between the set
of all possible monomials m2 such that (m1 · m2 ) is d-extremal and subsets of Z. To see this observe that
fixing m1 completely determines the degree of m2 with respect to any Y -variable21 x j —if j ∈ Y then
(
0 if degx j (m1 ) = 0,
degx j (m2 ) = (4.31)
d j − e j otherwise.
For the remaining variables, i. e., the Z-variables, the degree of m2 with respect to x j must be either 0 or
(d j − e j ) = d j . Define the subset of Z corresponding to m2 as
def
Sm2 = { j ∈ Z : degx j (m2 ) = d j }. (4.32)
We now use the homogeneity of gv+1 and proceed as in the proof of Lemma 4.8 (by considering here the
degree with respect to Z-variables) to deduce that the set
def
Im1 = {Sm2 : m2 is in gv+1 and (m1 · m2 ) is a d-extremal monomial} ⊆ 2Z (4.33)
forms an antichain in 2Z . So by Sperner’s theorem Im1 can have a size of at most
2Nv+1
|Z|
≤√ . (4.34)
|Z| /2 Nv+1
This proves the claim and hence the lemma as well.
The upper bound on the number of d-extremal monomials in a (d, v, L)-form follows immediately.
Proof of Lemma 4.6. Since T is in (d, v, L)-form by definition there exist pairs
(d1 , g1 ), (d2 , g2 ), . . . , (dv , gv )
such that each gi is multi-di -ic with
d = d1 + · · · + dv , T = g1 · g2 · · · · · gv , (4.35)
and !
def [
Ni = Supp(di ) \ Supp(d j ) ≥ L. (4.36)
j<i
Furthermore, since T is homogeneous, all the gi are homogeneous as well. Applying Lemma 4.9 we get
that the number of d-extremal monomials in T is at most
2N1 +N2 +···+Nv 2N
√ ≤ v/2 , (4.37)
N1 · N2 · · · · · Nv L
as required.
21 We say a variable x
j is a Y -variable iff j ∈ Y .
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 18
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
4.3 Putting things together
Our target polynomial is a multi-r-ic adaptation of the elementary symmetric polynomial obtained by
raising every variable to the r-th power. Specifically, let
!
PN,r (x1 , . . . , xN ) = ∑ ∏ xrj . (4.38)
S∈( [N]
) j∈S
N/2
N
Then PN,r is a homogeneous multi-r-ic polynomial of degree rN/2 which contains N/2 extremal
monomials. A relatively straightforward adaptation of an observation attributed to Michael Ben-Or [26]
implies that PN,r is easy to compute.
Proposition 4.11. Let F be a field which contains r distinct rth roots of unity and size of F is at least
(2Nr). The polynomial PN,r defined above can be computed by a multi-r-ic (nonhomogeneous) ΣΠΣ
circuit of size O(N 2 r) on F.
Proof. Let X1 , . . . , XN ,t be N + 1 variables. Let ξ1 , . . . , ξr be the r distinct rth roots of the unity. We
consider the polynomial
N r
Q(X,t) = ∏ ∏(X j − ξit). (4.39)
j=1 i=1
For all i ≤ r and all j ≤ N, we know that (X j − ξit) is a factor of (X jr − t r ) and so
N
Q(X,t) = ∏ (X jr − t r ). (4.40)
j=1
Then, for every integer p such that 0 ≤ p ≤ N, the coefficient of t pr in Q(X,t) is
[t pr ]Q(X,t) = ∑ (−1) p ∏ X jr = (−1) p ∑ ∏ X jr . (4.41)
S∈([N] j∈S
/ [N]
) j∈S
p) S∈(N−p
Consequently, PN,r = (−1)N/2 [t Nr/2 ]Q(X,t) . Moreover, if q is an integer which is not a multiple of p,
then the coefficient of t q in Q(X,t) is zero. Finally, we can extract any coefficient by interpolation: let
a1 , . . . , aN+1 be elements of F such that the elements ar1 , . . . , arN+1 are pairwise distinct (this is possible
since the size of F is at least r(N + 1)). We get
N+1 N+1 N r
PN,r = (−1)N/2 [t Nr/2 ]Q(X,t) = (−1)N/2 ∑ λk Q(X, ak ) = ∑ (−1)N/2 λk ∏ ∏(X j − ξi ak ) (4.42)
k=1 k=1 j=1 i=1
where λ1 , . . . , λN+1 are constants of F. The formula is of the required form.
We can finally prove Theorem 1.2.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 19
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
Proof of Theorem 1.2. Our target polynomial is the polynomial PN,r defined above. Suppose that it is
computed by a homogeneous multi-r-ic formula Φ of size s. Let r = (r, r,√ . . . , r). By Corollary 4.4, Φ
b
can be written as a sum, of size at most s, of homogeneous (r, blog(N)/4c, d Ne)-form polynomials. By
2
Lemma 4.6 each one of these polynomials can compute at most 2N /(2log N/16−log(N)/4 )-many r-extremal
N
monomials. But PN,r has N/2 -many r-extremal monomials. Therefore, using Proposition 3.1, we must
have
N
2
N/2 2log N/16
s≥ 2 ≥ √ = N Ω(log N) . (4.43)
N
2 /(2 log N/16−log(N)/4 ) 2N 3/4
The moreover part follows from Proposition 4.11.
5 Constant-depth homogeneous multi-r-ic formulas
We follow the same overall proof strategy as in the previous section to obtain a lower bound for
homogeneous multi-r-ic formulas of small product-depth. With definitions as in section 4, the depth
reduction for low-depth formulas that we obtain is:
Lemma 5.1. Let r ≥ 1 be an integer and r = (r, r, . . . , r). Let f be a degree-d polynomial computed by a
homogeneous certified multi-r-ic formula Φ of size s and product-depth bounded by p. For any positive
integer
1 d 1/p
v≤ , (5.1)
8r 2r
there exist s homogeneous (r, v, 2)-form polynomials T1 , T2 , . . . , Ts such that f = T1 + T2 + · · · + Ts .
This depth reduction proceeds in two stages. The following definition will help us describe the
structure of the output of the first stage.
Definition 5.2. Let d = (d1 , . . . , dN ) be an N-tuple of non-negative integers. We will say that a polynomial
T (x) is (d,t, L)-balanced if T is multi-d-ic and there exist t pairs (d1 , g1 ), (d2 , g2 ), . . . , (dt , gt ) where
each gi is a multi-di -ic polynomial such that
1. T = g1 · g2 · · · · · gt ,
2. d = d1 + d2 + · · · + dt , and
3. |Supp(di )| ≥ L for all i ∈ [t].
Let us notice that if a polynomial is (d, a, L)-balanced for a parameter a > t, then we can easily get a
(d,t, L)-balanced expression by grouping some factors.
The first stage flattens the formula into a sum of a small number of balanced polynomials and its
proof idea comes from [10]. Specifically, we have:
Lemma 5.3. Let r ≥ 1 be an integer and let r = (r, r, . . . , r). Let Φ be a certified multi-r-ic homogeneous
formula of product-depth p computing a polynomial of degree d ≥ 2r. For any positive integer
1/p
1 d
t≤ · (5.2)
4 2r
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 20
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
there exist homogeneous (r,t, 2)-balanced polynomials T1 , . . . , Ts such that s ≤ Size(Φ) and
b = T1 + · · · + Ts .
Φ (5.3)
Proof of Lemma 5.3. First let us note the following:
Claim 5.4. Let d, p, r and t be positive integers such that
1/p
1 d
d ≥ 2r and t ≤ · . (5.4)
4 2r
If Φ is a certified multi-r-ic homogeneous formula of product-depth p and of formal degree d ≥ 2r, then
there exists a product node α in Φ such that22 deg(α) ≥ 2r and for every child β of α it holds that
deg β < deg(α)/(4t). Moreover, Φ b α is (dα ,t, 2)-balanced.
Proof. First let us prove the existence of such a gate α by induction on p. We will see why Φ b α is
(dα ,t, 2)-balanced at the end of the proof.
If p = 1 and γ = γ1 × · · · × γv is a product node in Φ, then deg(γ) = d and deg(γi ) ≤ 1 < d/4t. So
we can set α = γ. Assume that p > 1, and let γ = γ1 × · · · × γv be a product node in Φ with deg(γ) = d.
If for every i ∈ [v], deg(γi ) < d/(4t), then we can again set α = γ. Otherwise there exists γi such that
deg(γi ) ≥ d/(4t). In this case, Φγi is of product-depth p0 < p and degree at least d/(4t). Using the
hypothesis over t, we know that
d deg γi 0 deg γi
(4t) p ≤ ≤ 4t , and then 1 ≤ (4t) p ≤ (4t) p−1 ≤ . (5.5)
2r 2r 2r
In particular,
1/p0
1 deg γi
deg γi ≥ 2r and t ≤ . (5.6)
4 2r
By the inductive assumption, there exists a product node α in Φγi (and so in Φ) such that deg(α) ≥ 2r
and for every child β of α, deg β < (deg α)/(4t).
We now show that Φ b α is (dα ,t, 2)-balanced. Let the children of α be β1 , β2 , . . . , βv . We greedily
merge pairs of polynomials (Φ bβ ,Φ
i
b β ) such that
j
Supp(dβi ) = Supp(dβ j ) = 1 and Supp(dβi ) 6= Supp(dβ j ) (5.7)
and also add the corresponding dβi and dβ j . This means that Φ
b α can be written as
b α = g1 · · · · · ga · h,
Φ where deg(h) ≤ r (5.8)
such that for each i ∈ [a], we have deg(gi ) < 2 · deg(α)/(4t) and the multi-degree label corresponding to
gi has support size at least 2 (the polynomial h contains the potential last polynomial Φβi of support one
which can not be merged). In particular,
2 deg(α) a 1
2r ≤ deg(α) ≤ a + r and so deg(α) ≤ + deg(α). (5.9)
4t 2t 2
22 Recall that for a node α, the total formal degree of α is denoted by deg(α) and that if a node alpha has certification
(d1 , . . . , dN ), then ∑i di is only an upper bound on deg(α).
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 21
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
This implies that a is at least t. Finally, rewriting Φ b α = g1 · · · · · ga−1 · (ga · h), we see that Φ
b α as Φ b α is
(dα , a, 2)-balanced where a ≥ t. This proves the claim.
Let α be a node given by Claim 5.4. By Proposition 4.3, there exist a d-certified homogeneous
formula Λ of product-depth at most p and a (d − dα )-certified homogeneous Ψ such that
Φ b ·Φ
b =Ψ b α + Λ.
b (5.10)
By induction on size, Λb can be expressed as a sum of at most Size(Λ)-many (d,t, 2)-balanced polynomials.
Now Φb α is (dα ,t, 2)-balanced and so (Ψb ·Φ
b α ) is (d,t, 2)-balanced (by grouping Ψ with another factor).
Altogether, Φ can be written as a sum of (d,t, 2)-balanced polynomials, the number of summands being
b
at most 1 + Size(Λ) ≤ Size(Φ). This proves the lemma.
Lemma 5.5. Let r, v ≥ 1 be integers and let t = 2rv. Let r = (r, r, . . . , r). If T (x) is a (r,t, 2)-balanced
polynomial then T (x) has a (r, v, 2)-form.
Proof. By the premise of the lemma, there exist pairs (d1 , f1 ), (d2 , f2 ), . . . , (dt , ft ) such that
T = f 1 · · · · · ft , r = d1 + · · · + dt , ∀i ∈ [t] Supp(di ) ≥ 2, fi is multi-di -ic. (5.11)
The proof is by reordering and regrouping the fi in a series of v steps. The following claim captures the
invariants after the k-th step of this process.
Claim 5.6. Let k ∈ [0..v] be any integer. There exists a partition [t] = A ] B ]C with |A| = k and an order
on the elements of A = {i1 , . . . , ik } such that
def
• fi1 · · · · · fik is in (e, k, 2)-form where e = di1 + · · · + dik ,
• |B| ≥ t − 2rk,
• and for all j ∈ B, Supp(d j ) \ Supp(e) ≥ 2.
Intuitively, the set A is the accumulator of good polynomials, B is the source of fresh polynomials
and C denotes the set of throwaway polynomials.
Proof. Let us prove the claim by induction on k.
Base case k = 0. For the base case of k = 0, we can choose A = C = 0/ (so that e = (0, 0, . . . , 0)) and
B = [t] and the claim is easily verified using Equation (5.11).
Inductive step. Assume k < v and let [t] = A ] B ]C be the partition obtained after the k-th step. Let
e = ∑i∈A di and let Z = [N] \ Supp(e) be the set of (indices of) variables which do not appear in A. We
can associate to each fi with i ∈ B the support of di in Z:
def
SuppZ (di ) = Supp(di ) ∩ Z. (5.12)
We choose a factor fu with u ∈ B such that the size of its corresponding support (Supp(du )) in Z is
minimum (as k < v, the set B is non-empty) and add it to A. We then remove from B the neighbouring
factors F defined as
def
F = { j ∈ (B \ {u}) : SuppZ (d j ) \ SuppZ (du ) ≤ 1}. (5.13)
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 22
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
The updated partition is given by
def def def
A0 = A ] {u}, B0 = B \ ({u} ∪ F), C0 = C ] F. (5.14)
To complete the induction, it suffices to verify that the size of B0 is large enough (the other conditions
follow from the choice of u and F). In particular, by induction hypothesis, we know that |SuppZ (du )| ≥ 2.
Z (du )| − 1 for all j ∈ F. Now counting the
As |SuppZ (du )| is minimal, SuppZ (du ) ∩ SuppZ (d j ) ≥ |Supp
occurrences of the variables in SuppZ (du ) in du + ∑ j∈F d j and using the fact that T is multi-r-ic we get
that
|SuppZ (du )| · r ≥ |SuppZ (du )| + (|SuppZ (du )| − 1) · |F| ≥ (|SuppZ (du )| − 1) · (|F| + 1). (5.15)
Hence
|SuppZ (du )|
|F| + 1 ≤ r · ≤ 2r. (5.16)
|SuppZ (du )| − 1
Thus
B0 = |B| − (|F| + 1) ≥ t − 2r(k + 1). (5.17)
This completes the proof of the inductive step and hence of the claim.
Let us come back to the proof of the lemma. The previous claim when k = v states that T can
def
be written as T = fi1 · · · · · fiv · h where fi1 · · · · · fiv is in (e, v, 2)-form and e = di1 + · · · + div . Hence
T = fi1 · · · · · fiv−1 · ( fiv · h) is in (r, v, 2)-form, as required.
Proof of Lemma 5.1. Let t = 2rv. Then we have
1p
1 d
t≤ · . (5.18)
4 2r
So we can apply Lemma 5.3. We get some (r,t, 2)-balanced multi-r-ic polynomials T1 , . . . , Ts such that
s ≤ Size(Φ) and f = T1 + · · · + Ts . By Lemma 5.5 each of these terms Ti has a (r, v, 2)-form.
Proof of Theorem 1.3. Our target polynomial is the polynomial PN,r defined in Equation (4.38) and used
previously in the proof of Theorem 1.2. It has degree d = rN/2. Suppose that it is computed by a
homogeneous multi-r-ic formula Φ of product-depth p and size s. Let r = (r, r, . . . , r). By Proposition 3.4,
there exists a labelling of the vertices of Φ such that the formula becomes certified multi-r-ic. Let
$ % $ %
1 d 1/p 1 N 1/p
v= = . (5.19)
8r 2r 8r 4
By hypothesis we have
−2 + log N
p≤ , (5.20)
4 + log r
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 23
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
it ensures that v is a positive integer. By Lemma 5.1, Φ can be written as a sum of at most s homogeneous
(r, v, 2)-form polynomials. By Lemma 4.6 each one N v/2
N
of these polynomials can compute at most 2 /(2 )-
many r-extremal monomials. But PN,r has N/2 -many r-extremal monomials. Therefore we must have
(using the hypothesis over p)
N
1/p
N/2 Ω 1r ·( N4 )
s ≥ N v/2 = 2 . (5.21)
2 /(2 )
The moreover part follows from Proposition 4.11.
Remark 5.7. We noticed that for proving Theorem 1.3, we just need in fact the weaker hypothesis
−2 + log N
p≤ . (5.22)
4 + log log N + log r
The hypothesis of the theorem ensures that the final lower bound is superpolynomial.
6 A lower bound for depth-three multi-r-ic circuits
6.1 The complexity measure
In this section we prove a lower bound for multi-r-ic depth-three circuits by employing some sort of
a hybrid of the complexity measures used by Raz [28] and by Nisan and Wigderson [26] and recently
introduced in [15] called dimension of skewed partials. We pick a suitable set of variables y ⊂ x, take k-th
order derivatives with respect to these variables (for a suitably chosen value of k), then set the y-variables
to zero and finally count the dimension of the resulting set of polynomials. In the notation introduced in
section 3 our measure is the dimension of the set
σy ∂ =ky f , (6.1)
which we denote by
dim σy ∂ =k
y f (6.2)
and we sometimes refer to it as the skewed partials complexity of f (SkPy -complexity of f for short).
6.2 Upper bounding the SkPy -complexity of a depth-three circuit
We first observe that in order to upper bound the SkPy -complexity of a ΣΠΣ-circuit C, it suffices to upper
bound the SkPy -complexity of a single term.
Proposition 6.1 (Sub-additivity of the complexity measure). For any pair of polynomials g(x), h(x) ∈ F[x]
and any subset of variables y ⊆ x and any integer k ≥ 0 we have
dim σy ∂ =k y (g(x) + h(x)) ≤ dim σy ∂ =k
y g(x) + dim σy ∂ =k
y h(x) . (6.3)
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 24
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
This is easily verified. We next derive an upper bound for the SkPy -complexity of a term T of a
multi-r-ic ΣΠΣ-circuit C by observing that the SkPy -complexity of T depends only on a relatively small
subset of the affine forms in T .
Lemma 6.2 (Upperbound on SkPy -complexity of a depth-three circuit). Let x = y ] z be any partition of
the variable set with |z| = m. If C is a multi-r-ic depth-three circuit (i. e., C = T1 + T2 + · · · + Ts , where
each T j is a product of affine forms and every variable occurs in at most r affine forms within a given T j )
then !
k
=k
m·r
dim σy ∂ y C ≤ s · ∑ . (6.4)
i=0 i
Proof. Let x = y z, where |z| = m. Consider a term T of our circuit C. T is a product of affine forms.
U
Since the term T is assumed to be multi-r-ic, we have that each z-variable appears in at most r affine
forms inside T . In particular, there are at most m · r affine forms in T which contain a z-variable. So let
T = `1 (y, z) · `2 (y, z) · · · · · `t (y, z) · Q(y), (6.5)
where t ≤ m · r, each `i (y, z) is an affine form that depends on some z-variable and Q(y) is the product
of all the affine forms in T which depend only on the y-variables. To prove the lemma it suffices (via
Proposition 6.1) to show that
k
=k
t
dim σy ∂ y T ≤∑ . (6.6)
i=0 i
It suffices to show that
( )
σy ∂ =k
y T ⊆ F-span ∏ σy (`i (y, z)) : S ⊆ [t], |S| ≥ (t − k) . (6.7)
i∈S
Since σy : F[x] 7→ F[x] is a F-linear map, this is in turn implied by
(( ) )
∂ =k
y T ⊆ F-span ∏ `i (y, z) : S ⊆ [t], |S| ≥ (t − k) · F[y] . (6.8)
i∈S
This last statement is easily seen by starting from the definition of T given by Equation (6.5) and
computing the appropriate derivatives.
6.3 A multilinear polynomial with high SkPy -complexity
So our problem boils down to finding an explicit polynomial f (x) such that
dim σy ∂ =k y f (x) (6.9)
is large. Additionally, it is desirable that f should be as easy to compute
as possible.
We show that there
23 =k
is a polynomial f computed by a small ΠΣΠ-circuit whose dim σy ∂ y f -complexity is large.
23 This polynomial is a restriction of the iterated matrix multiplication polynomial and is implicitly there in the work of
Fournier, Limaye, Malod and Srinivasan [6]. Vineet Nair pointed out to us that the relevant restriction of IMM as used here is in
fact computed by a small ΠΣΠ circuit.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 25
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
Lemma 6.3 (An explicit family with high SkPy -complexity). There is an explicit family of multilinear
polynomials { fn,k (x) : n, k ≥ 0} of degree d = 3k on N = (n2 · k + 2nk) variables such that there exists a
partition x = y ] z with |z| = m = 2nk and |y| = N − m = n2 k such that
dim σy ∂ =k y f n,k = n2k . (6.10)
Moreover, fn,k can be obtained as a restriction of IMMn,d+2k simply by substituting some subset of
variables in IMMn,d+2k to zero/one values.
Proof. We first give the description of the family of polynomials { fn,k (x) : k ≥ 0} along with the
associated partition of variables x = y ] z. From the description itself, it will be clear that fn,k has the
2
required degree and number of variables and is computed by a Π[k] Σ[n ] Π[3] -circuit. We first partition our
set of (n2 k + 2nk) variables into two sets
x = y ] z, where |z| = m = 2nk and |y| = N − m = n2 k. (6.11)
The y and z are further partitioned into k sets of equal size:
y = y1 ] y2 ] · · · ] yk , and z = z1 ] z2 ] · · · ] zk (6.12)
where for each i ∈ [k] we have |yi | = n2 and |zi | = 2n and the overall structure of fn,k is:
fn,k (y, z) = g1 (y1 , z1 ) · g2 (y2 , z2 ) · · · · · gk (yk , zk ) (6.13)
where each gi (yi , zi ) is a degree three polynomial over the indicated set of variables. For each i ∈ [k], yi will
consist of the n2 variables {yi,a,b : a, b ∈ [n]} and zi consists of the 2n variables {zi,a,b : a ∈ [n], b ∈ [2]}.
Finally define
def
gi (yi , zi ) = ∑ yi,a,b · zi,a,1 · zi,b,2 . (6.14)
a,b∈[n]
It remains to show that
dim σy ∂ =k
y f n,k = n2k . (6.15)
To see this note that any k-th order derivative of f with respect to the y-variables is either zero or a
monomial in the z-variables. There are (n2 )k nonzero derivatives of f with respect to the y variables
(obtained by picking exactly one variable from each yi , i ∈ [k]) and moreover these give rise to distinct
monomials in the z-variables and hence are linearly independent as well. Therefore,
dim σy ∂ =ky f n,k = (n2 )k = n2k , as required. (6.16)
For the moreover part, first note that from the definition of the family fn,k it follows that it is computed by
2
a multilinear-Π[k] Σ[n ] Π[3] -circuit. So it is a restriction of IMMn,d+2k .24
24 For more details refer to the subsequent Lemma 8.1.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 26
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
6.4 Putting things together
With the above upper and lower bounds in our hand, we are ready to prove a lower bound for multi-r-ic
ΣΠΣ-circuits.
Theorem 6.4. There exists an explicit family fn,k (x) of multilinear polynomials of degree d = 3k on
N = Θ(n2 d) variables such that fn,k is computed by a poly(n, d)-sized multilinear ΠΣΠ-circuit25 but any
multi-r-ic ΣΠΣ-circuit computing fn,k must have top fanin at least
3 n d/3
. (6.17)
d 2e · r
Proof of Theorem 6.4. Let fn,k (y, z) be the polynomial (family) along with the indicated partition of
variables as described in Lemma 6.3. Indeed, as it is noticed in the proof of Lemma 6.3, it is computed by
2
a multilinear-Π[k] Σ[n ] Π[3] -circuit. Suppose that a multi-r-ic ΣΠΣ circuit C of top fanin s computes fn,k .
Then by Lemma 6.2 and Lemma 6.3 we have
k !
2k
=k
(2nk) · r (2nk) · r
n = dim σy ∂ y fn,k ≤ s · ∑ ≤ s·k· . (6.18)
i=0 i k
Therefore
n2k n2k 1 n k
s≥ ≥ ≥ · , (6.19)
k· (2nk)·r 2nkre k k 2re
k k· k
as required.
As it was noticed before, the polynomial fn,k is a restriction of the iterated matrix multiplication
IMMn,d+2k . So, Theorem 1.7 directly follows from Theorem 6.4.
7 Depth-four multi-r-ic circuits with low support
As mentioned in the overview, we prove a lower bound for multi-r-ic ΣΠΣΠ circuits by first using random
restrictions to reduce the number of variables appearing in any monomial and then proving lower bounds
against such representations. Let us give names to such polynomials and circuits.
Definition 7.1 (Support size of a polynomial and low-support ΣΠΣΠ circuits). Let z ⊆ x be a subset of
variables. The support size of a polynomial f (x) ∈ F[x] (resp. the z-support size of f ) is the maximum
support size (resp. z-support size) of any monomial appearing in f . We will call a depth-four circuit C as
a τ-supported depth-four circuit, denoted by ΣΠΣΠ{τ} , if it is of the following form:
C = T1 + T2 + · · · + Ts , (7.1)
where each term Ti is of the form Ti = Qi1 · Qi2 · · · · · Qit where the support size of Qi j is lower than τ for
all i ∈ [s] and j ∈ [t].
We remark that the support size of f is the maximum of the sizes of the supports of the monomials of
f , which can be really smaller than the size of the set of the variables which appear in f .
25 More precisely, f [O(d)] Σ[O(N)] Π[O(1)] -circuit.
n,k is computed by a multilinear-Π
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 27
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
7.1 The complexity measure
Definition 7.2 (Shifted Skewed Partials). Let x = y ] z be a partition of our set of variables into two parts
y and z. For a polynomial f (x) ∈ F[x], define the dimension of shifted y-partials, SSP`,y,k ( f ) for short, as
follows:
def
SSP`,y,k ( f ) = dim z≤` · σy ∂ =k
y f . (7.2)
7.2 Upper bounding the SSP-complexity of a multi-r-ic low support depth-four circuit
Let C be a multi-r-ic depth-four circuit with z-bottom support bounded by τ. We now give an upper
bound on SSP`,y,k (C).
Proposition 7.3 (Sub-additivity of the complexity measure). For any pair of polynomials g(x), h(x) ∈ F[x]
and any partition of variables x = y ] z and any pair of integers k, ` ≥ 0 we have
SSP`,y,k (g(y, z) + h(y, z)) ≤ SSP`,y,k (g(y, z)) + SSP`,y,k (h(y, z)). (7.3)
We now provide the following upper bound on the SSP-complexity of a term of such a circuit.
Lemma 7.4 (Upper bound on the SSP`,y,k -complexity of a low support circuit.). Let x = y ] z be any
partition of variables. If C is a multi-r-ic ΣΠΣΠ-circuit of z-support at most τ and if C has top fanin s
then 2·m
m+`+k·r·τ
SSP`,y,k (C) ≤ s · τ · , where m = |z| . (7.4)
k m
Proof. By the subadditivity of our measure (Proposition 7.3), it suffices to prove a
2 · m/τ m+`+k·r·τ
· (7.5)
k m
upper bound for a term T which is of the form
T (y, z) = Q1 (y, z) · Q2 (y, z) · · · · · QD (y, z) · R(y), (7.6)
where each Qi (y, z) is a polynomial of z-support at most τ, R(y) is an arbitrary polynomial over the
indicated set of variables and T is multi-r-ic. Note that since each Qi has z-support at most τ and is
multi-r-ic, the z-degree of each Qi is at most r · τ. We first do a preprocessing part in which we focus
on the z-degree of the Qi and combine those with low z-degree. Specifically, if any two of the Qi have
z-degree less than r · τ/2 we multiply them together to obtain a new combined factor having z-degree at
most rτ. At the end, if it remains one Qi of z-degree less than rτ/2 and if we can multiply it with another
Qi without exceeding the z-degree rτ, we merge them. After this preprocessing, all the Qi but at most
one have z-degree greater than rτ/2 (and the last part cannot be merged), thus the average z-degree is at
least rτ/2. Now, since the polynomial T is multi-r-ic, its z-degree is at most rm. Hence
rτ
m · r ≥ degz (T ) = ∑ degz (Qi ) ≥ D · . (7.7)
i∈[D]
2
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 28
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
This yields the following upper bound on the number of factors D in T :
2m
D≤ . (7.8)
τ
Now it suffices to show that
!
[
z≤` · σy ∂ =k
y T ⊆ F-span ∏ σy (Qi ) · z≤(`+krτ) . (7.9)
i∈S
S∈ [D]
(D−k)
In turn, it suffices to show that
!
[
=k
σy ∂ y T ⊆ F-span ∏ σy (Qi ) · z≤(krτ) (7.10)
i∈S
S∈ [D]
(D−k)
which in turn follows from
!
[
=k ≤(krτ)
∂ y T ⊆ F-span ∏ i Q (y, z) · z · F[y] . (7.11)
i∈S
S∈ [D]
(D−k)
We show this last containment via induction on k. For k = 0, the containment in Equation (7.11) follows
from the definition of T Equation (7.6) itself. For the inductive step, suppose that g(y, z) ∈ ∂ =k
y T is a k-th
order derivative of T . By the inductive assumption we have that g(y, z) can be expressed as a F-linear
combination of polynomials of the form
!
h= ∏ Qi (y, z) · h1 (z) · h2 (y), (7.12)
i∈S
where
[D]
S∈ and h1 (z) ∈ z≤(k·r·τ) . (7.13)
(D − k)
Let
!
R= ∏ Qi (y, z) , (7.14)
i∈S
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 29
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
i0 ∈ S and y ∈ y be a variable. Differentiating Equation (7.12) with respect to y we have
∂h R ∂Qj R(y, z) ∂ h2 (y)
= ∑ · · h1 (z) · h2 (y) + · Qi0 (y, z) · h1 (z) ·
∂y j∈S Q j ∂ y Q i0 (y, z) ∂y
( ! )
[ R ∂Qj R(y, z)
∈ F-span · · z≤(krτ) · F[y] ∪ · Qi0 (y, z) · z≤(krτ) · F[y]
j∈S
Q j ∂ y Q i 0 (y, z)
( ! )
[ R
≤(rτ) ≤(krτ) R(y, z) ≤(rτ) ≤(krτ)
⊆ F-span ·z · F[y] · z · F[y] ∪ ·z · F[y] · z · F[y]
j∈S
Qj Qi0 (y, z)
( ! )
[ R R(y, z)
⊆ F-span · z≤((k+1)rτ) · F[y] ∪ · z≤((k+1)rτ) · F[y]
j∈S
Q j Q i0 (y, z)
!
[
≤((k+1)rτ)
⊆ F-span ∏ Q j · z · F[y]
A∈( S ) j∈A
(D−k−1)
!
≤((k+1)rτ)
[
⊆ F-span ∏ Qj ·z · F[y] .
j∈A
A∈ [D]
((D−(k+1)))
In the third step above we use the fact that Q j has z-degree at most rτ and hence for all j we have that Q j
∂Q
as well as ∂ y j is in
n o
F-span z≤(rτ) · F[y] .
This completes the induction step for the proof of Equation (7.11) and hence proves the lemma.
As an immediate corollary, we obtain an upper bound on the SSP-complexity of a multi-r-ic circuit
having bottom support bounded by τ.
7.3 A multilinear polynomial with high SSP-complexity
The explicit polynomial. Our explicit polynomial is a generalization of the one in section 6 for multi-
r-ic depth-three circuits.
Lemma 7.5. There exists an explicit family of polynomials Fn,d,k (y, z) such that for any δ ≤ 1/5, n ≥
3, d, k, ` we have
M 2 |z| + ` − (δ · α · k)
|z| + `
SSP`,y,k (Fn,d,k ) ≥ M · − · , (7.15)
|z| 2 |z|
where M = (n2−δ /2)k . Moreover, Fn,d,k can be obtained as a restriction of IMMn,d+2k simply by substi-
tuting some subset of variables in IMMn,d+2k to zero/one values.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 30
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
As the proof of the lemma is a bit technical, we postpone it at the end of the section (in subsection 7.6).
We now describe the family Fn,d,k of the lemma above. Let
def d − k
α= . (7.16)
2k
The polynomial Fn,d,k is of the form:
def
Fn,d,k (y, z) = g1 (y1 , z1 ) · g2 (y2 , z2 ) · · · · · gk (yk , zk ), (7.17)
where the gi are polynomials over the indicated (disjoint) subsets of variables defined as
def
gi (yi , zi ) = ∑ yi,a,b · ∏ zi,c,a · zi,c+α,b (7.18)
a,b∈[n] c∈[α]
so that the overall number of y-variables is |y| = (n2 ) · (k) and the overall number of z-variables is
|z| = (2αn) · (k). The degree of Fn,d,k (y, z) is d = (2α + 1) · k. The proof that this family has the
properties claimed in Lemma 7.5 is very similar to a corresponding one in the work of Fournier, Limaye,
Malod and Srinivasan [6]. For the sake of completeness, we included a proof at the end of the section.
7.4 Putting things together
Armed with these upper and lower bounds on SSP-complexity, we are now ready to prove the lower
bound for multi-r-ic ΣΠΣΠ{τ} -circuits.
Theorem 7.6. Let τ = τ(d) and any r = r(d) be integers such that rτ = o(d), rτ ≥ log n and r1.1 = o(n).
For26
d
k= ,
1 + 5000rτ
any multi-r-ic ΣΠΣΠ{τ} -circuit computing Fn,d,k must have top fanin at least
n Ω( r·τd )
. (7.19)
r1.1
k
Proof. Shorthands and choice of parameters. Let m = |z| and M = n2−δ /2 . Our main parameters
are chosen as
m·r·τ
α = 2500 · r · τ, ` = (7.20)
ε · β · ln n
wherein the underlying constants are further chosen as
1
ε = 2 · 10−4 , δ= , β = 200. (7.21)
25
Our polynomial Fn,d,k (x) is as described above.
26 By choosing a new d 0 (with d ≥ d 0 ≥ d/2) instead of d, we will always assume that k = εd/(ε + rτ) is an integer.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 31
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
Claim 7.7. For the above choice of parameters we have
m+` 1 2 m + ` − (δ · α · k) 1 m+`
M· − ·M · ≥ ·M· . (7.22)
m 2 m 2 m
Proof. We want to constraint β to ensure the claim, i. e.,
m + ` − δ αk m+`
M· ≤ . (7.23)
m m
Let us notice that the choice of parameters imply that
mα β
≥ ln(n). (7.24)
` 2
We have
m+`−(δ αk)
m (m + ` − δ αk)!`! (` − δ αk + 1) · · · · · (`)
M m+`
=M =M
(` − δ αk)!(m + `)! (m + ` − δ αk + 1) · · · · · (m + `)
m
δ αk δ αk
` m
≤M = M 1−
m+` m+`
mδ αk
≤ M · e− m+`
!k
n2−δ mδ αk
≤ · e− 2` (7.25)
2
δ β log(n) k
≤ 2(2−δ ) log(n)− 4
which is less than or equal to 1 as soon as
δβ 4(2 − δ )
2−δ − ≤ 0, i. e., β≥ . (7.26)
4 δ
For the inequaliy (7.25), we need ` ≥ m which is true if rτ ≥ log n, or more accurately if rτ ≥ εβ ln n.
From Lemma 7.4 we get that any multi-r-ic ΣΠΣΠ{τ} -circuit computing fd = Fn,d,k must have top
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 32
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
fanin at least
SSP`,y,k ( fd (y, z))
s≥ 2·m
· m+`+k·r·τ
τ
k m
M · m+` 2 · m+`−(δ ·α·k)
1
m − 2 · M m
≥ 2·m (using Lemma 7.5)
m+`+k·r·τ
τ
k
· m
1 m+`
· M ·
≥ 2·m2 m
(using Equation (7.22))
m+`+k·r·τ
τ
k
· m
1 M (m + `)! · m! · (` + krτ)!
≥ · 2·m k · (via binomial estimates from Section 3)
2 e· τ m! · `! · (m + ` + krτ)!
k
!k
1 n2−δ · k · τ (` + 1) · (` + 2) · · · · · (` + krτ)
= · ·
2 4e · m (m + ` + 1) · (m + ` + 2) · · · · · (m + ` + krτ)
!k
1 n2−δ · k · τ 1
= · · m m m
2 4e · (2αnk) (1 + `+1 ) · (1 + `+2 ) · · · · · (1 + `+krτ )
!k
1 2ε · n1−δ 1
= · · m m m
2 8e · r (1 + `+1 ) · (1 + `+2 ) · · · · · (1 + `+krτ )
!k
1 ε · n1−δ 1 m m
≥ · · m krτ (as 1 + ≤ 1+ ∀i ≥ 1)
2 4e · r (1 + `+1 ) `+i `+1
!k
1 ε · n1−δ m
≥ · · e− `+1 ·krτ (via exponential estimates from Section 3)
2 4e · r
1 ε k
≥ · · n(1−δ −εβ )
2 4e · r
d
n0.92 2α+1
1 1
= · ·
2 2 · 104 · e r
n Ω( rτd )
= 1.1 .
r
7.5 A multi-r-ic polynomial with high SSP-complexity
We also observe here that if our target polynomial is also allowed to be multi-r-ic (so that the total degree
of our target polynomial can be Θ(rN)) then we can obtain a significantly improved lower bound—a
lower bound that is independent of r (and exponential in (N/τ)).
Theorem 7.8. For any positive integers r = r(N) and τ = τ(N) with τ ≥ 2, rτ ≥ log n and τ = o(N),
there exists a (explicit) family {FN,r } of multi-r-ic N-variate polynomials such that FN,r is computed by a
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 33
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
poly(Nr)-sized multi-r-ic ΠΣΠ{760τ+1} -circuit but any multi-r-ic ΣΠΣΠ{τ} -circuit computing FN,r must
N
have top fanin at least 2Ω( τ ) .
Proof. Our target polynomial is just the same polynomial as in section 7.3 but wherein the z-variables are
raised to the r-th powers. In more detail, for positive integers n, k, r and α define the polynomial Fn,k,r,α
as follows.
def
Fn,k,r,α (y, z) = g1 (y1 , z1 ) · g2 (y2 , z2 ) · · · · · gk (yk , zk ), (7.27)
where the gi are polynomials over the indicated (disjoint) subsets of variables defined as
def
gi (yi , zi ) = ∑ yi,a,b · ∏ zri,c,a · zri,c+α,b (7.28)
a,b∈[n] c∈[α]
so that the overall number of y-variables is |y| = (n2 ) · (k) and the overall number of z-variables is
|z| = (2αn) · (k). The total number of variables in Fn,k,r,α is N = (n2 + 2αn) · k. The degree of Fn,k,r,α (y, z)
is d = (2αr + 1) · k. The choice of parameters is
τ m·τ ·r
α = , `= . (7.29)
2ε εβ ln n
The analogous lower bound in this case is that for any δ ≤ 1/5, n ≥ 3, d, `, k we have
M 2 |z| + ` − (δ · α · r · k)
|z| + `
SSP`,y,k (Fn,k,r,α ) ≥ M · − · , (7.30)
|z| 2 |z|
where M = (n2−δ /2)k . Then for proving Equation (7.30) is larger or equal to M |z|+`
|z|
/2, we need rτ ≥
εβ ln n. Thus taking r ≥ 1, τ ≥ 2 is sufficient for the choice of parameters given below. Combining this
with the upper bound for the circuit given by Lemma 7.4 and proceeding as in the proof of Theorem 7.6,
we finally arrive at a lower bound of
!k
ε · n(1−δ −εβ )
1 εN
s≥ with k = . (7.31)
2 4e εn2 + τn
If we now choose
1 1
δ= , ε= , n = 217 and β = 76, (7.32)
10 760
we get
s = 2Ω(N/τ) , as required. (7.33)
We recall that a ΣΠΣΠ circuit is called τ-supported if the product gates in the top layer have a support
of size at most τ. In particular, from a depth-3 ΣΠΣ circuit, it is possible to add a top layer of product
gates of fan-in one (and so of support one). So, by choosing τ = 2 in Theorem 7.8, it directly implies
Theorem 1.9.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 34
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
7.6 Proof of Lemma 7.5
Lemma 7.9 (Restatement of Lemma 7.5). There exists an explicit family of polynomials Fn,d,k (y, z) such
that for any δ ≤ 1/5, n ≥ 3, d, k, ` we have
M 2 |z| + ` − (δ · α · k)
|z| + `
SSP`,y,k (Fn,d,k ) ≥ M · − · , (7.34)
|z| 2 |z|
where M = (n2−δ /2)k . Moreover, Fn,d,k can be obtained as a restriction of IMMn,d+2k simply by substi-
tuting some subset of variables in IMMn,d+2k to zero/one values.
2
Proof. For any couple of k-uplets (a = (a1 , . . . , ak ), b = (b1 , . . . , bk )) in [n]k , let us define
def ∂ kF k
ya,b = (y1,a1 ,b1 , . . . , yk,ak ,bk ) and ∂ a,b (F) = = ∏ ∏ zi,c,ai · zi,c+α,bi . (7.35)
∂ ya,b i=1 c∈[α]
Notice that {∂∂ a,b (F)} is a subset of n2k monomials belonging to the set σy (∂∂ =k
y F). Hence,
SPP`,y,k (F) = dim(z≤` · σy (∂∂ =k ≤`
∂ a,b (F)}) = z≤` · {∂∂ a,b (F)} .
y F)) ≥ dim(z · {∂ (7.36)
The third step is due to the fact that the dimension of the vector space generated by a set of monomials is
exactly the cardinality of this set.
In the following, we will consider a subset of {∂∂ a,b (F)} made of monomials which are pairwise
sufficiently far away. For that, let us define some distances. If u and v are two k-vectors,
def
∆(u, v) = |{i | ui 6= vi }|. (7.37)
And then
def
∆ (∂∂ a1 ,b1 (F), ∂ a2 ,b2 (F)) = ∆(a1 , a2 ) + ∆(b1 , b2 ). (7.38)
Claim 7.10. There exists PM,δ a subset of {∂∂ a,b (F)} of cardinality M such that if ∂ a1 ,b1 (F) and ∂ a2 ,b2 (F)
are two distinct elements of PM,δ , then
∆ (∂∂ a1 ,b1 (F), ∂ a2 ,b2 (F)) ≥ δ · k. (7.39)
Proof. For any monomial m in {∂∂ a,b (F)}, there are at most δ2kk · nδ k monomials from {∂∂ a,b (F)} which
are at distance at most δ · k (for the distance ∆). In particular such a PM,δ can be obtained by a greedy
algorithm27 as soon as
2k
M· · nδ k ≤ |(∂∂ a,b (F))| = n2k . (7.40)
δk
It implies we can choose M as large as
" #k !k
n2k n(2−δ )k
δ
δ 2−δ n2−δ 1
2k δ k
≥ = ·n ≥ since δ ≤ . (7.41)
( 2ek
δk n δk )
δk 2e 2 5
27 The greedy algorithm adds monomials one by one to the set P
M,δ via the instruction: if there is still a monomial m which is
at a distance at least δ · k from all the monomials currently in PM,δ , we add the monomial m to PM,δ .
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 35
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
Then, with Equation (7.36),
[
SPP`,y,k (F) ≥ |z≤` · PM,δ | = z≤` · m
m∈PM,δ
1
≥ ∑ |z≤` · m| − 2 ∑ |(z≤` · m1 ) ∩ (z≤` · m2 )|. (7.42)
m∈PM,δ m1 6=m2 ∈PM,δ
Let us upperbound the cardinality |(z≤` · m1 ) ∩ (z≤` · m2 )| for any m1 6= m2 . For any m̃ in |(z≤` · m1 ) ∩
(z≤` · m2 )|, we have m̃ = m1 · m̃1 where m̃1 is a z-monomial of degree at most `. As ∆(m1 , m2 ) ≥ δ · k,
it implies there are at least δ kα variables {t1 , . . . ,tδ kα } which appear in m2 and not in m1 . So, these
variables have to appear in m̃1 . In particular, m̃ = m1 ·t1 · · · · ·tδ kα · m̃2 where m̃2 is a z-monomial of degree
at most ` − (δ αk). Consequently, for any pair of distinct monomials m1 , m2 of PM,δ ,
≤` ≤` |z| + ` − (δ αk)
|(z · m1 ) ∩ (z · m2 )| ≤ . (7.43)
|z|
Plugging this bound in Equation (7.42) directly implies the lemma.
8 Depth-four multi-r-ic circuits
In this section we give a lower bound for multi-r-ic ΣΠΣΠ circuits computing the iterated multiplication
polynomial, IMMn,d . The argument goes like this.28 It turns out that there is a large set S of restrictions
which when applied to IMM yields (an isomorphic copy of) the polynomial Fn,d,k from section 7.3. At the
same time, any small (multi-r-ic) ΣΠΣΠ-circuit C is converted to a small (multi-r-ic) low support ΣΠΣΠ
circuit under the action of a random restriction from S.29 Since Fn,d,k is hard for multi-r-ic low support
depth-four circuits (Theorem 7.6), we deduce that IMM must be hard for multi-r-ic ΣΠΣΠ circuits. The
next lemma is implicit in [6], however, to make this paper self-contained, we give a proof of it at the end
of this section.
Lemma 8.1 (Implicit in [6]). Let k, d, n be positive integers with d = (2α + 1)k where α is an integer.
Consider h(x) := IMMn,d+2k (x).30 There is a partition x = y]z and a large set S consisting of restrictions
σ : F[x] 7→ F[x] of size (n!)(d−k) with the following properties:
1. For each σ ∈ S, σ (h) is a polynomial isomorphic to the polynomial Fn,d,k (y, z) from section 7.3.
2. For any circuit C, σ (C) is a circuit of the same depth as C itself. Moreover, if C is multi-r-ic then so
is σ (C).
28 This part of the argument is essentially as in [6].
29 with high probability
30 In fact, h(x) := IMM
n,d+k+1 (x) is sufficient if one uses the original restriction from [6]. See the remark in the proof given
at the end of these section.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 36
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
3. If C is a depth-four circuit of size s then for any τ ≥ 1, with probability at least
e τ
p = 1−s· over the uniform, random choice of σ , (8.1)
n
σ (C) is a depth-four circuit with z-bottom support at most τ.
Combined with Theorem 7.6, this immediately yields the lower bound for multi-r-ic depth-four
circuits (without any restriction on the bottom support) given in Theorem 1.4.
Proof of Theorem 1.4. Let
$r %
d d
τ= and still k = . (8.2)
r 1 + 5000rτ
We give a proof by contradiction. Suppose it is the case that IMMn,d (x) has a multi-r-ic depth-four circuit
C of size
n o √d/r
s = 1.1 . (8.3)
r
√ k as chosen above, that IMMn,d+2k (x) also has a multi-r-ic depth-four circuit C of
This means that for
size s = (n/r1.1 )o( d/r) . So, for n large enough, s · (e/n)τ < 1. Applying Lemma 8.1 we obtain that there
exists31 a restriction σ : F[x] 7→ F[x] such that the following two properties hold:
1. σ (IMMn,d+2k ) is isomorphic to the polynomial Fn,d,k from section 7.3,
2. σ (C) is a depth-four circuit with z-bottom support at most τ.
Thus σ (C) computes (a polynomial isomorphic to) Fn,d,k . Moreover, as d ≥ log2 n, we have rτ ≥ log n.
Hence by Theorem 7.6, σ (C) must have top fanin at least
n Ω √ dr
n Ω( rτd )
= . (8.4)
r1.1 r1.1
But then the size s of C is at least as large as its top fanin which in turn is at least as large as the top fanin
of σ (C). Therefore
n Ω √ dr
s ≥ 1.1 , (8.5)
r
which contradicts the assumption in Equation (8.3). This proves the theorem.
31 Indeed, every restriction from the set S of Lemma 8.1 satisfies the first property, and any random restriction from S satisfies
the second one which high probability (larger than 1 − s · (e/n)τ ).
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 37
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
8.1 A multi-r-ic polynomial requiring large multi-r-ic depth-four circuits
In this section we exhibit an explicit multi-r-ic polynomial√in N variables such that any depth-four
multi-r-ic circuit computing it must have a size of at least 2Ω( N) .
Proof of Theorem 1.6. Our explicit polynomial is just a variant of IMMn,d 0 +2k obtained by raising some
of the variables to the r-th powers. Specifically, we want to let the exponent 1 for the x-variables which
will be sent to the y-variables during the restriction phase, and raise all others variables to the power r.
More formally, if we define τ, k and α as follows:
√ d
τ = b d 0 c, k= and α = 380τ (8.6)
1 + 760rτ
(we still have d 0 + 2k = (2α + 3) · k and d = (2αr + 1) · k as in Theorem 7.8),
then let IMMPn,d 0 ,r (x) denote the following polynomial:
def e
l,a,b
IMMPn,d 0 ,r = IMMn,d 0 +2k (xl,a,b ) (8.7)
where (
1 if l is of the form i(2α + 3) + α + 2 for i integer,
el,a,b = (8.8)
r otherwise.
From the above definition, it is clear that IMMPn,d 0 ,r is an explicit multi-r-ic polynomial computed by
a poly(nd 0 r)-sized algebraic branching program. Our explicit family of polynomials GN,r is simply
IMMPn,d 0 ,r for n being a suitably large constant. Specifically, let n = 217 . The number of variables
N = n2 · (d 0 + 2k − 2) + 2n and hence d 0 = Θ(N) as n is constant.
The rest of the proof is very similar to that of Theorem 1.4 and we sketch √
it below. Suppose it
o( N )
is the case that there is a multi-r-ic depth-four circuit C of size at most 2 computing IMMPn,d 0 ,r .
Using the same set of restrictions as in the proof of Theorem 1.4, we obtain that there exists a restriction
σ : F[x] 7→ F[x] such that
1. σ (IMMPn,d 0 ,r ) is a polynomial isomorphic to the polynomial FN,r from Theorem 7.8;
√
2. σ (C) is a multi-r-ic depth-four circuit with bottom support at most τ = Θ N .
√
√
But this means that σ (C) is a multi-r-ic depth-four circuit of bottom fanin τ = Θ( N) and top fanin
2o( N) that computes (a polynomial isomorphic to) FN,r , contradicting
√
Theorem 7.8. Hence any multi-r-ic
Ω( N )
depth-four circuit computing GN,r must have a size of at least 2 .
8.2 Proof of Lemma 8.1
We reprove here a result which is implicit in [6].
Lemma 8.2 (Restatement of Lemma 8.1). Let k, d, n be positive integers with d = (2α + 1)k where α is
an integer. Consider h(x) := IMMn,d+2k (x). There is a partition x = y ] z and a large set S consisting of
restrictions σ : F[x] 7→ F[x] of size (n!)(d−k) with the following properties:
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 38
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
1. For each σ ∈ S, σ (h) is a polynomial isomorphic to the polynomial Fn,d,k from section 7.3.
2. For any circuit C, σ (C) is a circuit of the same depth as C itself. Moreover, if C is multi-r-ic then so
is σ (C).
3. If C is a depth-four circuit of size s then for any τ ≥ 1, with probability at least
e τ
p = 1−s· over the uniform random choice of σ , (8.9)
n
σ (C) is a depth-four circuit with z-bottom support at most τ.
Proof. Let Sn be the set of the permutations of [n] and let L = 2 + d/k = 2α + 3.
Let first define the set of the restrictions. In fact, we will give in the same time a renaming of
the variables which highlights the isomorphism to Fn,d,k . For any sequence of n-permutations π =
(π1,1 , . . . , πk,2α ) ∈ (Sn )k·2α we will define the restriction σπ . We want each restriction σπ (h) be a product
of k polynomials.
1 1 1 1 1 1
1 1 1 1 1 1
n 1 1 1 1 1 1
A1 A2 Ak
1 1 1 1 1 1
1 1 1 1 1 1
2α + 1
L
More formally, for any matrix Ml with
• l ≡ 1 mod L, we set (
1 if a = 1,
xl,a,b = (8.10)
0 otherwise,
• l ≡ 0 mod L, we set (
1 if b = 1,
xl,a,b = (8.11)
0 otherwise.
Remark 8.3. In the proof from [6], we can notice that the groups of two consecutive constant matrices
(last matrix from a block and first matrix of the next block) are merged together. We choose this
presentation since it highlights the fact that the restriction is a product of length k.
Now, we want to define the restriction for the other matrices.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 39
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
Ai u yi,u,v
zi,2,u
n v
πi,1 πi,2 πi,α πi,α+1 πi,2α
α
Complete
Bipartite Graph
More formally, for any matrix Ml with
• l = (i − 1)L + α + 2, we set xl,a,b = yi,a,b ,
• l = (i − 1)L + q + 1 with 1 ≤ q ≤ α, we set
(
0 if πi,q (a) 6= b,
xl,a,b = (8.12)
zi,q,c otherwise where c = πi,α ◦ πi,α−1 ◦ · · · ◦ πi,q+1 (b),
• l = (i − 1)L + q + 2 with α + 1 ≤ q ≤ 2α, we set
(
0 if πi,q (a) 6= b,
xl,a,b = (8.13)
zi,q,c otherwise where a = πi,q−1 ◦ πi,q−2 ◦ · · · ◦ πi,α+1 (c).
The set of these restrictions will be denoted by S. Then, for any σ ∈ S, the polynomial σ (h) (where the
renaming of the variables is done as above) equals Fn,d,k , which proves the point 1). The size of S is
(n!)2αk = (n!)d−k
as required.
The property 2) is immediate since
1. for any x ∈ x, for any σ ∈ S, σ (x) is a constant (in {0, 1}) or a variable (in y ] z)
2. and if σ (x1 ) = σ (x2 ) ∈ y ] z then x1 = x2 .
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 40
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
Finally, let us prove the point 3). We uniformly randomly pick a sequence π of n-permutations. Let A
and B be two subsets of Sn . So, for i 6= j the events πi ∈ A and π j ∈ B are independent. Let x0 ⊆ x be the
subset of the variables which can be transformed into a z-variable. More formally,
x0 = {xi,a,b | ∃p, q ∈ N s.t. i = pL + q, p < k and (2 ≤ q ≤ α + 1 or α + 3 ≤ q ≤ 2α + 2)}. (8.14)
For simplicity, we will also re-index the variables in x0 = (xi,q,a,b )1≤i≤k,1≤q≤2α by skipping the matrices
which do not contain x0 -variables.
(
x if q ≤ α,
xi,q,a,b = (i−1)L+q+1,a,b (8.15)
x(i−1)L+q+2,a,b otherwise.
Let t be a monomial computed at the first level of the circuit C of x0 -support larger than τ. Let us define
Ci,q = {(a, b) | xi,q,a,b is a variable of t}. (8.16)
In particular, we have
∑|Ci,q | ≥ τ. (8.17)
i,q
The restrictions σπ (t) will be sent to 0 as soon as one of the x0 -variable xi,q,a,b of t is sent to 0, i. e., as
soon as there exists a x0 -variable xi,q,a,b in t such that πi,q (a) 6= b.
Hence,
h i
Pπ [σπ (t) 6= 0] = Pπ πi,q (a) = b | ∀xi,q,a,b ∈ (x0 ∩ t)
k 2α
= ∏ ∏ Pπi,q ∈Sn [πi,q (a) = b | ∀(a, b) ∈ Ci,q ] . (8.18)
i=1 q=1
The last equality holds since the events are independent.
Let us fix i and q, we will prove
Claim 8.4.
e |Ci,q |
def
Pi,q = Pπi,q ∈Sn [πi,q (a) = b | ∀(a, b) ∈ Ci,q ] ≤ . (8.19)
n
Proof. In the proof, c will denote the cardinality |Ci,q |. The inequality is true if c = 0. Moreover, if (a, b1 )
and (a, b2 ) are in Ci,q with b1 6= b2 , then πi,q (a) 6= b1 or πi,q (a) 6= b2 and so Pi,q = 0. Hence, we can
assume that 1 ≤ c ≤ n. Let Ci,q = {(a1 , b1 ), . . . , (ac , bc )}. The number of n-permutations π such that for
all j ∈ [c], π(a j ) = b j is exactly the number of (n − c)-permutations, i. e., (n − c)!. Then, using Stirling’s
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 41
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
approximation32
(n − c)!
Pi,q =
(n)!
n − c n−c e n n − c e
r
≤ √
e n n 2π
e c 1
c n−c+ 2 e
≤ 1− √
n n 2π
e c 2 e
−c+ cn − 2n
c
≤ e √
n 2π
e c 2 e
n
−n+ nn − 2n
≤ e √
n 2π
e c r e
=
n 2π
e c
≤ (8.20)
n
where the fifth step comes from the fact that the function
x2
x
−x + − (8.21)
n 2n
with 1 ≤ x ≤ n is maximized when x = n.
Finally, using Equation (8.17), Equation (8.18) and Equation (8.19)
k 2α |Ci,q |
e e τ
Pπ [σπ (t) 6= 0] ≤ ∏ ∏ ≤ . (8.22)
i=1 q=1 n n
So, the probability with which a term with x0 -support larger than τ is still present after the restriction is at
most (e/n)τ . By hypothesis, there are at most s terms, so the union bound implies that the probability
that the restriction of the circuit does not contain any term with z-support larger than τ is at least
1 − s · (e/n)τ .
9 Discussion
One motivation behind this work was to generalize the results of [28, 30] from r = 1 which corresponds
to multilinear formulas to arbitrary r. While we do make some progress towards this goal, the original
problem(s) which motivated this work remain open:
Open Problem 9.1. Prove super-polynomial lower bounds for constant-depth multi-r-ic formulas (for
some explicit family of polynomials).
Open Problem 9.2. Prove super-polynomial lower bounds for multi-r-ic formulas (for some explicit
family of polynomials).
√
32 n n 2πn ≤ n! ≤ n n √
e e e n.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 42
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
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. Press, 2008. [doi:10.1109/FOCS.2008.32] 2
[2] N OGA A LON AND J OEL S PENCER: The Probabilistic Method. Wiley Online Library, 2010.
[doi:10.1002/9780470277331] 16
[3] P ETER B ÜRGISSER , M ICHAEL C LAUSEN , AND M OHAMMAD A MIN S HOKROLLAHI: Algebraic
Complexity Theory. Springer, 1997. [doi:10.1007/978-3-662-03338-8] 2
[4] S URYAJITH C HILLARA AND PARTHA M UKHOPADHYAY: Depth-4 lower bounds, determi-
nantal complexity: A unified approach. In Proc. 31st Symp. Theoretical Aspects of Comp.
Sci. (STACS’14), pp. 239–250. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2014.
[doi:10.4230/LIPIcs.STACS.2014.239, arXiv:1308.1640] 2
[5] Z EEV DVIR , A MIR S HPILKA , AND A MIR Y EHUDAYOFF: Hardness-randomness tradeoffs for
bounded depth arithmetic circuits. SIAM J. Comput., 39(4):1279–1293, 2009. Preliminary version
in STOC’08. [doi:10.1137/080735850] 2
[6] H ERVÉ F OURNIER , N UTAN L IMAYE , G UILLAUME M ALOD , AND S RIKANTH S RINIVASAN:
Lower bounds for depth-4 formulas computing iterated matrix multiplication. SIAM J. Comput.,
44(5):1173–1201, 2015. Preliminary version in STOC’14. [doi:10.1137/140990280] 2, 5, 25, 31,
36, 38, 39
[7] D IMA G RIGORIEV AND M AREK K ARPINSKI: An exponential lower bound for depth 3 arithmetic
circuits. In Proc. 30th STOC, pp. 577–582. ACM Press, 1998. [doi:10.1145/276698.276872] 5
[8] A NKIT G UPTA , P RITISH K AMATH , N EERAJ K AYAL , AND R AMPRASAD S APTHARISHI: Ap-
proaching the chasm at depth four. J. ACM, 61(6):33:1–33:16, 2014. Preliminary version in CCC’13.
[doi:10.1145/2629541] 2, 7
[9] A NKIT G UPTA , P RITISH K AMATH , N EERAJ K AYAL , AND R AMPRASAD S APTHARISHI: Arith-
metic circuits: A chasm at depth 3. SIAM J. Comput., 45(3):1064–1079, 2016. Preliminary version
in FOCS’13. [doi:10.1137/140957123] 2
[10] PAVEL H RUBEŠ AND A MIR Y EHUDAYOFF: Homogeneous formulas and symmetric polynomials.
Comput. Complexity, 20(3):559–578, 2011. [doi:10.1007/s00037-011-0007-3, arXiv:0907.2621] 6,
20
[11] L AURENT H YAFIL: On the parallel evaluation of multivariate polynomials. SIAM J. Comput.,
8(2):120–123, 1979. Preliminary version in STOC’78. [doi:10.1137/0208010] 2
[12] N EERAJ K AYAL: An Exponential Lower Bound for the Sum of Powers of Bounded Degree
Polynomials. Electron. Colloq. on Comput. Complexity (ECCC), 19:81, 2012. 2, 7
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 43
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
[13] N EERAJ K AYAL , N UTAN L IMAYE , C HANDAN S AHA , AND S RIKANTH S RINIVASAN: A super-
polynomial lower bound for regular arithmetic formulas. In Proc. 46th STOC, pp. 146–153. ACM
Press, 2014. [doi:10.1145/2591796.2591847] 2
[14] N EERAJ K AYAL , N UTAN L IMAYE , C HANDAN S AHA , AND S RIKANTH S RINIVASAN: An exponen-
tial lower bound for homogeneous depth four arithmetic formulas. SIAM J. Comput., 46(1):307–335,
2017. Preliminary version in FOCS’14. [doi:10.1137/151002423] 2, 6, 7
[15] N EERAJ K AYAL , V INEET NAIR , AND C HANDAN S AHA: Separation between read-once oblivious
algebraic branching programs (ROABPs) and multilinear depth three circuits. In Proc. 33rd Symp.
Theoretical Aspects of Comp. Sci. (STACS’16), pp. 46:1–46:15. Schloss Dagstuhl–Leibniz-Zentrum
fuer Informatik, 2016. [doi:10.4230/LIPIcs.STACS.2016.46] 24
[16] N EERAJ K AYAL AND C HANDAN S AHA: Lower Bounds for Sums of Products of Low arity
Polynomials. Electron. Colloq. on Comput. Complexity (ECCC), 22:73, 2015. 5
[17] N EERAJ K AYAL AND C HANDAN S AHA: Lower bounds for depth-three arithmetic circuits with
small bottom fanin. Comput. Complexity, 25(2):419–454, 2016. Preliminary version in CCC’15.
[doi:10.1007/s00037-016-0132-0] 2, 5
[18] N EERAJ K AYAL AND C HANDAN S AHA: Multi-k-ic depth three circuit lower bound. Theory Comput.
Syst., 61(4):1237–1251, 2017. Preliminary version in STACS’15. [doi:10.1007/s00224-016-9742-9]
2
[19] N EERAJ K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS: On the size of homogeneous and
of depth four formulas with low individual degree. In Proc. 48th STOC, pp. 626–632. ACM Press,
2016. [doi:10.1145/2897518.2897550] 1
[20] PASCAL KOIRAN: Arithmetic circuits: The chasm at depth four gets wider. Theoret. Comput. Sci.,
448:56–65, 2012. [doi:10.1016/j.tcs.2012.03.041, arXiv:1006.4700] 2
[21] M RINAL K UMAR AND R AMPRASAD S APTHARISHI: An exponential lower bound for ho-
mogeneous depth-5 circuits over finite fields. In Proc. 32nd Conf. on Computational Com-
plexity (CCC’17), pp. 31:1–31:30. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017.
[doi:10.4230/LIPIcs.CCC.2017.31, arXiv:1507.00177] 2
[22] M RINAL K UMAR AND S HUBHANGI S ARAF: The limits of depth reduction for arithmetic formulas:
It’s all about the top fan-in. SIAM J. Comput., 44(6):1601–1625, 2015. Preliminary version in
STOC’14. [doi:10.1137/140999220, arXiv:1311.6716] 2
[23] M RINAL K UMAR AND S HUBHANGI S ARAF: Sums of products of polynomials in few vari-
ables: Lower bounds and Polynomial Identity Testing. In Proc. 31st Conf. on Computational
Complexity (CCC’16), pp. 35:1–35:29. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016.
[doi:10.4230/LIPIcs.CCC.2016.35, arXiv:1504.06213] 2, 5
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 44
O N THE S IZE OF H OMOGENEOUS AND OF D EPTH -F OUR F ORMULAS WITH L OW I NDIVIDUAL D EGREE
[24] M RINAL K UMAR AND S HUBHANGI S ARAF: On the power of homogeneous depth 4 arith-
metic circuits. SIAM J. Comput., 46(1):336–387, 2017. Preliminary version in FOCS’14.
[doi:10.1137/140999335, arXiv:1404.1950] 2, 6, 7
[25] M RINAL K UMAR AND S HUBHANGI S ARAF: Arithmetic circuits with locally low algebraic rank.
2018. [arXiv:1806.06097] 5
[26] N OAM N ISAN AND AVI W IGDERSON: Lower bounds on arithmetic circuits via partial
derivatives. Comput. Complexity, 6(3):217–234, 1996. Preliminary version in FOCS’95.
[doi:10.1007/BF01294256] 19, 24
[27] R AFAEL O LIVEIRA: Factors of low individual degree polynomials. Comput. Complexity, 25(2):507–
561, 2016. Preliminary version in CCC’15. [doi:10.1007/s00037-016-0130-2] 2
[28] R AN R AZ: Multi-linear formulas for permanent and determinant are of super-polynomial size. J.
ACM, 56(2):8:1–8:17, 2009. Preliminary version in STOC’04. [doi:10.1145/1502793.1502797] 2,
5, 7, 24, 42
[29] R AN R AZ: Tensor-rank and lower bounds for arithmetic formulas. J. ACM, 60(6):40:1–40:15, 2013.
Preliminary version in STOC’10. [doi:10.1145/2535928] 2
[30] R AN R AZ AND A MIR Y EHUDAYOFF: Lower bounds and separations for constant depth mul-
tilinear circuits. Comput. Complexity, 18(2):171–207, 2009. Preliminary version in CCC’08.
[doi:10.1007/s00037-009-0270-8] 5, 7, 42
[31] R AMPRASAD S APTHARISHI: A survey of lower bounds in arithmetic circuit complexity, 2016.
Available at GitHub. 2
[32] A MIR S HPILKA AND A MIR Y EHUDAYOFF: Arithmetic circuits: A survey of recent results and
open questions. Foundations and Trends, 5(3–4):207–388, 2010. [doi:10.1561/0400000039] 2, 6
[33] E MANUEL S PERNER: Ein satz über untermengen einer endlichen menge. Mathematische Zeitschrift,
27(1):544–548, 1928. [doi:10.1007/BF01171114] 16
[34] S ÉBASTIEN TAVENAS: Improved bounds for reduction to depth 4 and depth 3. Inform. and Comput.,
240:2–11, 2015. Preliminary version in MFCS’13. [doi:10.1016/j.ic.2014.09.004, arXiv:1304.5777]
2
[35] L ESLIE G. VALIANT: Completeness classes in algebra. In Proc. 11th STOC, pp. 249–261. ACM
Press, 1979. [doi:10.1145/800135.804419] 4
[36] L ESLIE G. VALIANT, S VEN S KYUM , S TUART J. B ERKOWITZ , AND C HARLES R ACKOFF: Fast
parallel computation of polynomials using few processors. SIAM J. Comput., 12(4):641–644, 1983.
Preliminary version in MFCS’81. [doi:10.1137/0212043] 2
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 45
N EERAK K AYAL , C HANDAN S AHA , AND S ÉBASTIEN TAVENAS
AUTHORS
Neeraj Kayal
Researcher
Microsoft Research India
Bangalore, India
neeraka microsoft com
https://www.microsoft.com/en-us/research/people/neeraka/
Chandan Saha
Assistant professor
Indian Institute of Science
Bangalore, India
chandan iisc ac in
http://drona.csa.iisc.ernet.in/~chandan/
Sébastien Tavenas
CNRS Researcher
Université Savoie Mont Blanc
Chambéry, France
sebastien tavenas univ-smb fr
http://www.lama.univ-savoie.fr/~tavenas/
ABOUT THE AUTHORS
N EERAJ K AYAL graduated from I.I.T. Kanpur in 2006; his advisor was Manindra Agrawal.
His thesis focused on questions in algorithmic number theory and algorithmic algebra.
Since 2008, he has been with Microsoft Research India located in Bangalore.
C HANDAN S AHA received his Ph. D. from the Indian Institute of Technology Kanpur in
2010, where he was advised by Manindra Agrawal. During 2010-2012, he was a
postdoc in the Algorithms and Complexity group, headed by Kurt Mehlhorn, at MPII.
Chandan is interested in complexity theory, particularly arithmetic circuit complexity,
and computational algebra.
S ÉBASTIEN TAVENAS graduated from ENS Lyon in 2014; his advisors were Pascal Koiran
and Natacha Portier. His thesis focused on the relations between arithmetic lower bounds
and real algebraic geometry. After spending fifteen months as a postdoc in Bangalore
where he started collaboration with the two other authors of this paper, he returned to
France in 2016. Now, he lives in Chambéry in Savoie where he enjoys the proximity of
the lake and especially the mountains.
T HEORY OF C OMPUTING, Volume 14 (16), 2018, pp. 1–46 46