Research Highlights
Computing Applications

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

In the realm of algebraic complexity, this work brings a better understanding of hardness, identity testing, and reconstruction.

Posted
chair-lift on a snow-covered mountain
Read the related Technical Perspective

Abstract

An Algebraic Circuit for a multivariate polynomial P is a computational model for constructing the polynomial P using only additions and multiplications. It is a syntactic model of computation, as opposed to the Boolean Circuit model, and hence lower bounds for this model are widely expected to be easier to prove than lower bounds for Boolean circuits. Despite this, we do not have superpolynomial lower bounds against general algebraic circuits of depth 3 (except over constant-sized finite fields) and depth 4 (over any field other than 𝔽2), while constant-depth Boolean circuit lower bounds have been known since the early 1980s.

In this paper, we prove the first superpolynomial lower bounds against algebraic circuits of all constant depths over all fields of characteristic 0. We also observe that our super-polynomial lower bound for constant-depth circuits implies the first deterministic sub-exponential time algorithm for solving the Polynomial Identity Testing (PIT) problem for all small-depth circuits using the known connection between algebraic hardness and randomness.

 

1. Introduction

1.1. Algebraic complexity

The central questions of Complexity theory, such as P vs. NP, have proven to be difficult because it is hard to understand and capture the power of general algorithms. As a result, there have been many distinct lines of research focusing on restricted kinds of algorithms. Quite often, these capture all the approaches we have for solving certain families of computational problems, and thus are interesting objects of study in their own right.

This work is in the area of Algebraic Complexity, which is one such line of inquiry that has received a considerable amount of attention in the last few decades (for example, see the book4 or the surveys.13,19,20,22 Here, we study algebraic problems that are closely related to multivariate polynomials over some fields 𝔽 which we will assume to be the complex numbers ℂ in this paper. An example of such a polynomial in 3 variables of degree 3 is

P ( x 1 , x 2 , x 3 ) = x 1 + x 2 + x 3 + x 1 x 2 + x 2 x 3 + x 1 x 3 + x 1 x 2 x 3 .

Many natural algorithmic problems can be stated as the problem of evaluating one or more multivariate polynomials at an input point. Important examples of such problems include the Fast Fourier Transform, the Determinant and Matrix Multiplication. Some problems of this form are also expected to be computationally intractable, such as the Permanent.25 Given such a computational problem, it is natural to consider algorithms that are themselves somewhat algebraic, and use only natural operations such as additions and multiplications. This brings us to the Algebraic Circuit model, which is defined by a sequence of instructions, each involving sums (or more generally linear combinations) and products, at the end of which we produce the polynomial P we are interested in evaluating. An algebraic circuit for P gives us a recipe to evaluate P at any given point.a

An algebraic circuit is typically visualized as a directed acyclic graph as in Figure 1 (left) where the intermediate nodes (i.e., gates) represent the basic instructions. The efficiency of the computation is captured by the size of the circuit, which is defined to be the number of edges in the underlying graph (one could also look at the number of gates, which is within a quadratic factor of the number of edges). Another parameter of efficiency is the depth of the circuit, which is the length of the longest path in the computation. The depth captures the extent to which the algorithm is parallelizable. When the underlying graph is a tree, the circuit is said to be a formula.b

Left: an algebraic circuit. Right: a depth-2 algebraic circuit suggested by Equation (1).

Given a computational problem specified by a polynomial P, we would like to study the smallest size of an algebraic circuit (or formula) for P. In particular, there are many situations where we would like to show that a given polynomial has no small algebraic circuits. Analogous to the P vs. NP question in standard complexity theory, the principal question of this area is the Valiant’s P vs. Valiant’s NP (VP vs. VNP) question, which can equivalently be stated as the following “lower bound” question: show that the Permanent polynomial, which is a polynomial in N = n2 variables of degree n has no algebraic circuits of size poly(N).

As the algebraic circuit model is required to construct the formal polynomial P under consideration, it is a syntactic model of computation, as opposed to the Boolean circuit model, which is typically only required to output the correct answer on certain inputs (e.g., Boolean inputs). As a consequence, it is intuitive that the algebraic circuit yields a more restricted family of algorithms than its Boolean variant. In particular, this implies that the problem of proving algebraic circuit lower bounds is easier than its Boolean counterpart.3 On the other hand, it is also a natural model that captures most algorithms for algebraic computational problems of the kind we care about. Resolving the VP vs. VNP question is thus seen as an important stepping stone to resolving P vs. NP.

1.2. Constant-depth circuits

What makes the VP vs. VNP question (and other similar questions in algebraic complexity) particularly alluring is that there is a very concrete strategy for resolving it based on the technique of depth-reduction. To describe this, let us start with some basic notation. A polynomial P can always be written as a sum of monomials as in Equation (1) above. Such a representation can also be visualized as a depth-2 circuit (see Figure 1 right) and is called a ΣΠ circuit for the reason that the polynomial is expressed as a sum of products of variables. Such a representation is extremely simple to analyze: for example, any polynomial P has a unique such minimal representation, the size of which is essentially the number of monomials in the polynomial. For a polynomial in N variables of degree d, this is typically around Nd.

However, things get much more interesting with just one more layer of complexity. For instance, consider ΣΠΣ circuits, which are sums of products of sums of variables. Such circuits can be much more succinct than SP. For instance, the polynomial from Equation (1) can be written more succinctly as

( 1 + x 1 ) ( 1 + x 2 ) ( 1 + x 3 ) 1 ,

which can be seen as a simple ΣΠΣ circuit. More generally, a surprising and beautiful result of Gupta et al.9 (building on many previous results1,12,24) showed that if a polynomial P on N variables of degree d has an algebraic circuit of size poly(N), then it has a ΣΠΣ circuit of size NO(d). While this is quite large, it is still considerably smaller than the trivial Nd in the ΣΠ case. In particular, it is feasible that we could show VP is not VNP simply by showing that the Permanent (or another similar polynomial) has no ΣΠΣ circuits of this size!

In terms of depth, ΣΠΣ circuits are just depth-3 circuits. So this means that a strong enough lower bound for depth-3 circuits implies a separation between VP and VNP. No such connection between constant-depth circuit lower bounds and general circuit lower bounds is known in the non-algebraic (i.e., Boolean) setting.

In particular, the results above illustrate how useful it would be to have strong constant-depth circuit lower bounds in the algebraic setting. Unfortunately, however, these bounds have so far been difficult to demonstrate. Despite extensive work in the area, and many beautiful lower bound results against restricted models of circuits,8,15,16 even super-polynomial lower bounds against ΣΠΣ circuits have remained an open question.

In this work, we show superpolynomial lower bounds against general ΣΠΣ circuits and more generally, against circuits whose depth is a constant independent of the number of variables and the degree of the underlying polynomial. More precisely we show the following.

Theorem 1 (Main Result).

Let N, d be growing parameters with d = o(log N). There is an explicit polynomial PN,d(x1, …, xN) that has no algebraic circuits of constant depth and polynomial size. More precisely, for any fixed Δ, there is a constant ε > 0 such that any circuit of depth Δ computing PN,d has size at least NΩ(dε).

In the case of ΣΠΣ circuits (i.e., Δ = 3), we get a lower bound of NΩ(d). By the result of Gupta et al.9 mentioned above, any asymptotic improvement in the exponent in this bound could potentially separate VP from VNP.

Moreover, the polynomial PN,d itself is easy to describe and encodes the natural problem of Matrix Multiplication. Assume n and d are such that N = dn2. The polynomial PN,d is the Iterated Matrix Multiplication polynomial IMMn,d on N = dn2 variables, defined as follows. The underlying variables are partitioned into d sets X1, …, Xd of size n2, each of which is visualized as an n × n matrix with distinct variable entries. Then IMMn,d is defined to be the polynomial that is the (1, 1)th entry of the product matrix X1 · X2Xd.

1.3. Consequence of polynomial identity testing

Another important question in algebraic complexity deals with the algorithmic analysis of a given algebraic circuit. More specifically, the Polynomial Identity Testing (PIT) problem is the following algorithmic problem: given an algebraic circuit C computing a polynomial P, is this polynomial a nonzero polynomial? That is, are any of the coefficients of P non-zero?

To illustrate the hardness of this question, it is worth noting that the number of potential monomials in the polynomial P is exponentially large, and hence expanding out to compute each of the coefficients of P would take exponential time. Nevertheless, it is known that there is a polynomial-time randomized algorithm for this problem. We simply evaluate P at a random point and check if P evaluates to a non-zero value at that point. The circuit representation allows for efficient evaluation of P and hence this algorithm is efficient. However, the algorithm might make an error: specifically, this happens when P is non-zero but the algorithm happens to choose a point where P evaluates to zero. However, the probability of this can be shown to be small.

The algorithmic challenge is therefore to come up with a deterministic (i.e., non-randomized) efficient algorithm for this polynomial. This problem has seen extensive work over the past couple of decades (see e.g., the surveys13,20,22), with the introduction of many specialized tools to solve restricted variants of this problem. Nevertheless, even sub-exponential time deterministic algorithms for PIT for simple classes such as ΣΠΣ circuits remained open until this work.

The difficulty of this problem is explained by the strong connections that have been made between this question and the problem of showing lower bounds against algebraic circuits. An influential result of Kabanets and Impagliazzo11 showed that superpolynomial lower bounds against general algebraic circuits imply deterministic sub-exponential time algorithms for general PIT. Later results have tried to extend this algebraic hardness vs. randomness framework in several different ways.5,6,13 Specifically, Dvir et al.6 proved that hardness for constant-depth circuits implies a deterministic algorithm for PIT for constant-depth circuits. In a recent paper, Chou et al.5 refined this result and improved the dependence on the degree of the polynomial.

We observe that this result from Chou et al.5 combined with our lower bound from Theorem 1 gives the first sub-exponential time deterministic algorithm for PIT for algebraic circuits of any constant depth. Specifically, we get the following.

Corollary 2.

The following holds for any ε > 0. Let C be an algebraic circuit of size s ≤ poly(n) and constant depth Δ computing a polynomial on n variables. There is a deterministic algorithm that can check whether the polynomial computed by C is identically zero or not in time (sΔ+1n)O(nε).

2. The Approach: “Hardness Escalation”

While lower bounds against general algebraic circuits have been hard to prove, we do have several beautiful results against restricted kinds of algebraic circuits, such as Homogeneous, Multilinear, and Set Multilinear circuits. As these will be useful in the sequel, we review some of these definitions below.c

Recall that a multilinear polynomial P(x1, …, xN) is one in which each variable xi has degree at most 1, and a homogeneous polynomial is one that is a linear combination of monomials of the same total degree. If the underlying variable set is partitioned into d variable sets X1, …, Xd, then P is said to be set-multilinear with respect to this variable partition if P is a linear combination of monomials that contains one variable from each variable set among X1, …, Xd; note that a set-multilinear polynomial is both multilinear and homogeneous (of degree d). For example, the n × n Determinant is a set-multilinear polynomial w.r.t the variable partition corresponding to the rows of the underlying matrix, and the polynomial IMMn,d defined above is set-multilinear w.r.t. the partition into matrices X1, …, Xd.

Given a set-multilinear polynomial P (w.r.t. variable partition X1, …, Xd), it is natural to look at algebraic circuits computing P that themselves have the same structure. In particular, an algebraic circuit is said to be set-multilinear if each internal gate computes a set-multilinear polynomial in a subset of X1, …, Xd. Similarly, a multilinear or homogeneous circuit is one where each internal node computes a multilinear or homogeneous polynomial respectively. For each such restricted type of circuit, we have nontrivial lower bounds on the sizes of circuits computing explicit polynomials (also restricted in the same way).14,15,16 An important result of Nisan and Wigderson15 proved lower bounds against small-depth set-multilinear and homogeneous circuits computing IMMn,d. Building upon this, Raz16 showed superpolynomial lower bounds on the size of any (unbounded depth) multilinear formula computing the n × n Determinant and Permanent.

It is natural to ask if we can use these lower bounds against restricted kinds of circuits to prove lower bounds against more general algebraic circuits. Such “hardness escalation” results have appeared in many areas in computational complexity, including Algebraic complexity theory. Strassen23 and Raz17 both observed (in different settings) that lower bounds against small-depth circuits computing low-degree polynomials imply lower bounds against larger depth circuits. More recently, Raz18 showed that if a homogeneous or set-multilinear polynomial of degree d has an algebraic formula of size s, then it also has a homogeneous or set-multilinear formula of size poly(s) · (log s)O(d) respectively. In particular, for a homogeneous (resp. set-multilinear) polynomial P of degree d = O(log N / log log N), it follows that P has a formula of size poly(N) if and only if P has a homogeneous (resp. set-multilinear) formula of size poly(N).d

The latter result implies that if we could prove homogeneous or set-multilinear formula lower bounds of the form Nωd(1) (i.e., the exponent goes to infinity with d) for a polynomial P with N variables and degree d, then we would have superpolynomial general algebraic formula lower bounds. In particular, this would imply lower bounds against constant-depth algebraic circuits, as any constant-depth algebraic circuit can be converted to an algebraic formula with only a polynomial blow-up.e

Unfortunately, known results do not yield such lower bounds. In the homogeneous case, we have strong lower bounds against certain formulas of depth at most 4,14,15 but this falls short of proving anything for general formulas as Raz’s “homogenization” result does not preserve the depth of the formula (in fact, known results for homogeneous formulas stop yielding lower bounds exactly in the regime where they would yield implications for general circuits). In the set-multilinear, and more generally multilinear case, we do have lower bounds against formulas of large depth,15,16 but all such lower bounds are of the form f (d) · poly(N) where f (d) is a superpolynomial (and subexponential) function of d. With analogy to Parameterized Complexity Theory, we call such bounds Fixed Parameter Tractable (FPT) bounds. Our motivating question is if we can prove strong non-FPT lower bounds against restricted types of circuits or formulas in a setting where we can use them for lower bounds for general algebraic circuits or formulas. We show that this is indeed possible.

2.1. Technical results

Our main lower bound result is a strong non-FPT lower bound against constant-depth set-multilinear circuits, considerably strengthening known results in this direction.

We prove our lower bounds for the IMMn,d polynomial on N = dn2 variables as defined above. This polynomial has a simple divide-and-conquer-based set-multilinear formula of size nO(log d), and more generally for every Δ ≤ log d, a set-multilinear formula of depth 2Δ and size nO(Δd1/Δ). It is reasonable to conjecture that this simple upper bound is tight up to the constant in the exponent for set-multilinear formulas.

This has been shown for set-multilinear, and more generally, for homogeneous circuits of depths 3 and 4.7,14,15 However, as far as we know, no superpolynomial non-FPT lower bounds were known for any depths greater than 4, even under the set-multilinearity restriction. We show such lower bounds for all constant depths.

Theorem 3 (Lower bound against set-multilinear circuits).

Assume d ≤ (log n)/100. For any constant depth Δ, any set-multilinear circuit C computing IMMn,d of depth at most Δ must have size at least ndε, where ε is a constant that depends only on Δ. In the particular case that Δ = 5, the size of C must be at least nΩ(d).

With these stronger non-FPT lower bounds for set-multilinear circuits in place, we are able to derive lower bounds against stronger families of algebraic circuits via hardness escalation arguments.

First, we show that any homogeneous circuit of depth Δ and size s computing a set-multilinear polynomial P of degree d can be converted to a set-multilinear circuit with the same depth for P of size s · dO(d). Putting this together with Theorem 3, we get the first superpolynomial lower bounds (FPT or non-FPT) for homogeneous circuits of depth greater than 5.

Corollary 4 (Lower bound against homogeneous circuits).

Assume d ≤ (log n)/100. For any constant depth Δ, any homogeneous circuit C computing IMMn,d of depth at most Δ must have size at least ndε, where ε is a constant that depends only on Δ. In the particular case that Δ = 5, the size of C must be at least nΩ(d).

Note that our improved non-FPT bounds are crucial for deriving the above result from Theorem 3. The previous best lower bound of 2Ω(d) due to Nisan and Wigderson15 does not suffice for this, because of the dO(d) blow-up involved in converting a homogeneous circuit to one that is set-multilinear.

Next, we show that any (possibly non-homogeneous) algebraic circuit of depth Δ and size s computing a homogeneous polynomial P of degree d can be converted to a homogeneous circuit for P of depth 2Δ + 1 and size 2O(d). This implies the main result Theorem 1.

3. An Illustration: Depth-3 Circuits

We prove in this section the case Δ = 5 of Theorem 3 and Corollary 4 and the case Δ = 3 of Theorem 1.

3.1. Reduction to set-multilinear depth 5

In the next sub-section, we will show super polynomial lower bounds for small-degree polynomials against set-multilinear formulas of some constant depth. We want to extend these lower bounds to the general setting (i.e., without the set-multilinearity constraint).

Raz18 showed that if there is a fanin-2 formula of size s and depth Δ that computes a set-multilinear polynomial over the disjoint sets (X1, …, Xd), then there exists also a fanin-2 set-multilinear formula of size O((Δ+2)ds) and depth Δ that computes the same polynomial. However, the fanin-2 constraint is an issue when we want to deal with constant-depth circuits.

We show here that we can get a similar result for circuits with arbitrary fanins at the cost of a size blow-up of dO(d) poly(s) and an increase of the depth by a factor of at most 2.

Proposition 5.

Let s, N, d be growing parameters with sNd. If C is a circuit of size at most s and depth at most 3 computing a set-multilinear polynomial P over the sets of variables (X1, …, Xd) (with |Xi| ≤ N), then there is a set-multilinear circuit C˜ of size dO(d)poly(s) and depth at most 5 computing P.

Similar to Raz’s approach, we start by homogenizing the circuit and then we set-multilinearize it. In particular, the previous proposition is just the composition of Lemmas 6 and 7.

Non-homogeneous to homogeneous circuits.

It was already noticed9,10 that we can convert nonhomogeneous formulas of depth 3 to homogeneous formulas of depth 5 with a relatively small size blow-up.

Indeed, a general ΣΠΣ circuit of size s yields a formula of the following kind

F = Σ i = 1 s Π j = 1 s i , j

where each li,j is an affine linear polynomial in the underlying variables. Note that the individual summands of the expression may compute polynomials of degree s, which is possibly much larger than d. The main observation is that, assuming that the underlying field 𝔽 has characteristic 0 (which is the case here since we chose 𝔽 = ℂ), the homogeneous degree-d part of each summand can be computed by a homogeneous formula of size poly(s) · exp((Od)). Replacing each of these terms with such a formula, we see that the same polynomial can also be computed by a homogeneous ΣΠΣΠΣ formula of size size poly(s) · exp((Od)).f

The main observation is also easy to prove. Consider any summand Ti = li,1li,s. It suffices to prove the observation in the case that each li,j has a non-zero constant term cj (it is easy to reduce to this case). In this case, we can write

Γ i = ( Π j = 1 s c i ) Π j = 1 s ( 1 + i , j )

where each i,j is a homogeneous linear polynomial. It then follows that the degree-d homogeneous part Ti,d of Ti can be written as a linear projection applied to the Elementary Symmetric Polynomial Esd of degree d in s variables. More precisely, we have

T i , d = ( Π i = 1 s c i ) E s d ( i , 1 , , i , s ) .

Shpilka and Wigderson21 [Theorem 5.3] proved that, over fields of characteristic 0 the polynomial Esd has a homogeneous ΣΠΣΠ circuit of size poly(s) · exp(O(d)). The result seems to be also proved independently in Hrubeš and Yehudayoff.10 Using this with the above expression, we get the following result.

Lemma 6 (Lemma 5.6 in the journal version)9.

Let s, N, d be growing parameters. Fix any ΣΠΣ circuit F of size at most s computing a homogeneous polynomial P(x1, …, xN) of degree d. Then, P can also be computed by a homogeneous ΣΠΣΠΣ circuit F′ of size at most size poly(s) exp(O(d)).

Homogeneous to set-multilinear circuits.

Then we need to convert homogeneous circuits into set-multilinear ones without increasing the depth and with a relatively small size blow-up. In fact, this transformation is not really more complicated in the case of an arbitrary depth. Thus, we place ourselves here directly in this case.

Lemma 7.

Let Δ be an odd integer. Let s, N, d be growing parameters with sNd. If C is a homogeneous circuit of size at most s and depth at most Δ computing a set-multilinear polynomial P over the sets of variables (X1, …, Xd) (with |Xi| ≤ N), then there is a set-multilinear circuit C˜ of size at most (d!)s and depth at most Δ computing P.

Proof. Let us describe our new circuit C˜. For any gate α of degree dα from C, we create dαd gates αS in C˜ (we index these gates by the subsets S⊆[d] such that |S| = dα). Now we want to link these gates such that for every gate α in C and any S⊆[d] with |S| = dα, the depth of αS is the same as the one of α and the polynomial computed by αS is the projection of the polynomial computed by α to the set-multilinear part associated with S:

α S = Σ m set-multilinear over ( X i ) i s ( [ m ] α ) m

where ([m]α) is the coefficient of the monomial m in α.

Let us do it by induction on the structure of the graph.

If α is a leaf, it is labeled either by a constant or by a variable. When dα = 0, there is nothing to change. Otherwise dα = 1. In C the leaf α is labeled by a variable x which belongs to Xi. We just need to label the gates by α{i} = x and α{j} = 0 for ji.g

If α = c1α1 + … + αpαp is a sum gate (where the ci are constants in ℂ), we just need to compute the linear combination part by part. For any S⊆[d] with |S| = dα:

α S = c 1 α S 1 + + c p α S p .

Finally, if α = α1 · … · αp is a product gate, we need to extract all the decompositions. Let S⊆[d] with |S| = dα:

α S = Σ ( S 1 , , S p ) partition of S with i , | S i | = d α i α S 1 1 + + α S p p .

The size of the sum is (dαdα1,,dαp).

Hence each leaf and sum gate α in C creates (dαd)d! new gates in C˜. Each multiplication gate α in C creates (dαd)d! sum gates and (ddα)(dαdα1,,dαp)d! new product gates. So the number of gates of C˜ is bounded by 2d! times the number of gates of C. Notice that we can avoid factor 2 since we do not need to keep the sum gates which come from a product gate, we can merge them with the sum gates of the next layer of the circuit. (We always assume that the output gate is a sum gate, and so there is always a next layer to merge with.) Furthermore, the depth of the gate αS in C˜ is the same as the one of the gate α in C.

3.2. Lower bounds against set-multilinear depth 5

By Proposition 5, it is sufficient to get a sufficiently large lower bound against set-multilinear depth-5 circuits to prove Theorem 1 for depth-3 circuits.

In this section, we will prove the following non-FPT lower bound against set-multilinear depth-5 circuits.

Lemma 8.

Let n, d ∈(N){0} withn4d+1. Any set-multilinear circuit C of depth 5 computing IMMn,d has size at least nΩ(d).

Notice that if d ≤ (log n)/100, then the hypothesis of this lemma is immediately satisfied. Consequently, this lemma directly implies the case Δ = 5 of Theorem 3.

In the case where Δ = 3 in Theorem 1 using Proposition 5, we can transform circuit C into a depth-5 set-multilinear one of size at most dO(d)poly(s). By Lemma 8, it implies that dO(d)poly(s)nΩ(d). By the assumption d ≤ (log n)/100, we get the desired lower bound for s.

The case Δ = 5 of Corollary 4 is proved identically by replacing Proposition 5 with Lemma 7.

Therefore, all we have to do is prove Lemma 8. The proof technique is very standard: we will focus on the complexity measure of partial derivatives (introduced by Nisan and Wigderson15) and show that particular polynomials computed by small set-multilinear circuits of depth 5 have small measures. The novelty here is that we will focus on polynomials which are lopsided, that is, that are based on a partition of the variables where different parts have different sizes. It is thanks to this point that we are able to obtain new lower bounds.

The complexity measure.

So let us start by introducing the measure.

We will consider the set of words on an alphabet A⊆ℕ{0}. Let w = (w1, …, wd)∈ Ad For a subset S⊆[d], let wS denote ∑i∈S wi. We say is wAd b-unbiased if |w[t]|≤b for every td. We define Pw={i|wi>0} and Nw={i|wi<0} that is, the positive and negative indices of w respectively.

Given w, we denote by X¯(w) a tuple of d sets of variables (X(w1), …, X(wd) ) where |X(wi)|=2|wi|. We denote by 픽sm[𝒯] the set of set-multilinear polynomials over the tuple of sets of variables 𝒯.

Let MwP and MwN denote the sets of the set-multilinear monomials over only the positive and only the negative variable sets. Let fFsm[X¯(w)] we define Mw(f) as the matrix of size |MwP|×|MwN|, where the rows are indexed by MwP and the columns by MwN and where the coefficient at the entry (m1, m2) is the coefficient of the monomial m1m2 in f.

We associate with the space Fsm[X¯(w)] the standard rank-based complexity measure relrkw (short for “relative rank”) defined as follows. Let fFsm[X¯(w)] and define

[ r e l r k w ( f ) = r a n k ( M w ( f ) ) | M w P | | M w N | = r a n k ( M w ( f ) ) 2 1 2 Σ i [ d ] | w i | .

Intuitively, as we will want to play on the size of the subsets of variables and thus modify the maximum rank that the polynomial can have, using the relative rank rather than the usual rank allows us to more easily take into account the distance we are from the maximum rank.

We use the following properties of relrkw.

Claim 9.
  1. (Imbalance) SayfFsm[X¯(w)] Then, relrkw(f)2|w[d]|/2.

  2. (Sub-additivity) Sayf,gFsm[X¯(w)]. Then relrkw(f + g) ≤ relrkw(f) + relrkw(g).

  3. (Multiplicativity) Say f = f1 · f2·…· ft and assume that for each i[t],fiFsm[X¯(w|Si)] where (S1, …, St) is a partition of [d] and for each i[t],w|Si stands for the sub-word of w indexed by Si. Then relrkw(f)=relrkw(f1f2ft)=Πi[t]relrkw|si(fi).

Proof. We have that |MwP|=2ΣiPwwi and |MwN|=2ΣiNwwi. So 2|wd| is just the ratio of the larger dimension of Mw(f) by the smaller one. As the rank of a matrix is bounded by the minimum between its number of rows and its number of columns, it implies the first inequality of the claim.

The subadditivity property directly follows from the facts that Mw(f + g) = Mw(f) + Mw(g) and that the rank of a matrix is subadditive.

The multiplicative argument is standard too. As the product is set-multilinear, it implies that the matrix Mw(f1 · … · ft) is the matrix Mw(f1)⊗…⊗Mw(ft) where the symbol ⊗ stands for the Kronecker product. Finally, the rank is known to be multiplicative with respect to the Kronecker product. So,

r e l r k w ( f 1 f 2 f t ) = r a n k ( M w ( f 1 f t ) ) 2 1 2 j [ d ] | w j | = Π i [ t ] r a n k ( M w ( f i ) ) 2 1 2 j s i | w j = Π i [ t ] r e l r k w | S i ( f i ) .

Word polynomials and iterated matrix multiplication polynomial.

We said we will prove lower bounds for lopsided polynomials. Unfortunately, all variables parts of the polynomial IMMn,d have the same size (which is n2). In fact, we will prove the lower bound for the word polynomial which is a “set-multilinear” projection of IMMn,d (The projection is called set-multilinear because it preserves the set-multilinearity). So let us define this polynomial.

Let wAd be any word. For any such word, we define a polynomial Pw. Say X¯(w)=(X1,,Xd) and since each Xi has size 2|wi|, we assume that the variables of Xi are labeled by strings in {0,1}|wi|.

Given any monomial mFsm[X¯(w)] let m+ denote the corresponding “positive” monomial from MwP+ and m the corresponding “negative” monomial from MwN. As each variable of X¯(w) is labeled by a Boolean string and each set-multilinear monomial over any subset of X¯(w) is associated with a string of variables, we can associate any such monomial m′ with a Boolean string σ(m′). More precisely, if j1 < … < jt and m=xσ1(j1)xσ2(j2)xσt(jt) with xσi(ji)Xji and σi{0,1}|wji| for each i∈[t], then σ(m′) is defined to be σ1σt. If w is b-unbiased, the difference of length of the strings σ(m+) and σ(m) is at most b. We will write σ(m+) ~ σ(m) when the shorter one is a prefix of the other one.

The polynomial Pw is defined as follows:

P w = Σ m F [ X ¯ ( w ) ] , σ ( m + ) ~ σ ( m ) m .

Clearly, the matrices Mw(Pw) are full-rank (i.e., have a rank equal to either the number of rows or the number of columns, whichever is smaller). So, relrkw(Pw)=2|w[d]|/22b/2.

We observe that Pw can be obtained as a set-multilinear restriction of IMMn,d for an appropriate choice of n. Formally, one can show the following. The proof is straightforward but omitted from this extended abstract.

Lemma 10.

Let w ∈ Ad be any word which is b-unbiased. If there is a set-multilinear circuit computingIMM2b,dof size s and depth Δ, then there is also a set-multilinear circuit of size s and depth Δ computing a polynomialPwFsm[X¯(w)]such that relrkw(Pw) ≥ 2b/2.

Proof of Lemma 8.

We now have all the ingredients to tackle the proof of the lemma.

It is a standard fact that any circuit of constant depth can be converted to a formula with only a polynomial blow-up. So it suffices to show the following.

Claim 11.

Let d ≥ 16 and k>2d be an integer. Let w be any word of length d on the alphabet {k,kk/d}. Then any set-multilinear formula C of depth 5 and of size s satisfies

[ r e l r k w ( C ) s 2 k d 8 .

Indeed, by fixing k=log2n we have k>2d. We can construct by induction a word w on the alphabet {k,kk/d} which is k-unbiased. Indeed, if |w[i]| ≤ 0, we choose wi+1=kk/d, otherwise we set wi+1 = −k. By Lemma 10 and Claim 11, we get the lower bound:

s 2 k d 8 2 k 2 ( log 2 n 1 ) d 8 log 2 n n d 8 2 log 2 n l 6 log 2 n n d 8 17 16

for the polynomial IMM2k,d against set-multilinear circuits of depth 5.

Proof of Claim 11. We know C is a depth 5 formula, so we can define C = C1 + … + Ct where each Ci is of the form ΠΣΠΣ and has size si. We say that Ci is of type 1 if some factor of Ci has degree d/2, otherwise it is of type 2.

  • If Ci is of type 1, then Ci=Ci,1Ci,ti. Up to reordering, we can assume that Ci,1 is a sum of products of linear forms of degree at least d/2. Notice that if L is a linear form on variables X(wi), we have relrk(L)2|wi|/22(kk/d2)/2. In particular, by the multiplicativity and sub-additivity of relrkw (Claim 9), relrkw(Cj)relrkw(Ci,1)si2kdkd2ddeg(Ci,1)sj2kdkd4sj2kd8.

  • If Ci is of type 2, then Ci=Ci,1Ci,ti where each factor Cij has degree <d/2. Each Cij is a set-multilinear formula over a subset (X(wp): pSj) for some Sj ⊆[d] where S1,,Sti partition [d]. Let wi1,witi be the corresponding decomposition of w. That is, wij=w|Sj. Recall that for a word wij we defined in the preliminaries wSjij as the sum of its entries.

    Let j∈[ti]. Let aij be the number of positive indices in wij. If 2aij ≤ deg(Ci,j), then

    w S j i j k 2 d deg ( C i , j ) .

    Otherwise, we have

    | w S j i j | = | a i j k k d ( deg ( C i , j ) a j j ) k |        = | a j j k a i j k d deg ( C i , j ) k + a i j k |       > ( 2 a i j deg ( C i j ) a j j d ) k a i j       > k 2 k 4 = k 2 1 2       > k deg ( C i , j ) 2 d .

    So in both cases, |WSjij|kdeg(Ci,j)2d.

    In particular, relrkw(Ci)Πj=1ti212|wSjij|2kd4dsi2kd8.

The result of the claim directly follows from the subadditivity of the measure.

4. What Happens for Larger Constant Depths

To prove Theorem 1, Theorem 3, and Corollary 4 in their generality (i.e., for any constant depths), we generalize the depth-3 approach detailed above. To do that, we just need to generalize Proposition 5 and Lemma 8 for a larger depth. We will just sketch here the ideas to obtain such a generalization. The detailed proof of the main theorem can be found in the full version of this paper.

4.1. The set-multilinearization transformation

As already noticed the set-multilinearization from homogeneous circuits transformation (Lemma 7) still works for large depths. The only point there is to generalize Lemma 6 to a larger depth. Unlike the case of depth-3, this homogenization step was not known before this work. Now, inputs of a product can have now polynomials of any degree. The idea is to consider now some weighted versions of the elementary symmetric polynomials to take care of these degrees. The main difficulty now is to check that the Newton identities (which play a key role in the proof of Lemma 6) still hold in this weighted setting. But finally, we can obtain the following homogeneization result.

Lemma 12.

Let Δ be an odd integer. Let s, N, d be growing parameters with sN. If C is a circuit of size at most s and depth at most Δ computing a homogeneous polynomial P(x1, …, xN) of degree d, then, P can also be computed by a homogeneous circuit C˜ of size at most poly(s)2O(d) and depth at most 2Δ − 1.

4.2. Lower bounds for set-multilinear circuits

Then, we follow a similar path to obtain lower bounds on the size of set-multilinear circuits of any constant depth computing lopsided polynomials. In particular, we still consider the partial derivative measure. The idea now is to refine the alphabet which is used (taking values which depend on the depth Δ) so that the case where Ci is of type 2 in the proof can be tackled. Then the first case (Ci is of type 1) will correspond to an induction step.

Putting these steps in a more precise way, we can obtain the following generalization of Proposition 5 and so obtain a complete proof of Theorem 1.

Lemma 13.

Let Δ be an odd integer and let Γ = (Δ − 1)/2. Let n, d, Δ ∈ ℕ{0} with n ≥ 210d+1. Any set-multilinear circuit C of depth Δ computing IMMn,d has size at least

n Ω ( d 1 / ( 2 Γ 1 ) Γ ) .

Acknowledgments

The authors are grateful to R. Saptharishi for spending time to discuss the proof with us. Nutan Limaye was partially funded by SERB project File no. MTR/2017/000909. Sébastien Tavenas was funded by the project BIRCA from the IDEX of Univ. Grenoble Alpes (Contract 183459). He also benefited from accommodation paid by IIT Bombay during a visit of the other two authors.

    References

    • 1. Agrawal, M., and Vinay, V. Arithmetic circuits: A chasm at depth four. In Proceedings of Foundations of Computer Science (FOCS), USA. (2008), 6775; DOI: 10.1109/FOCS.2008.32.
    • 2. Beame, P. et al.  Hardness amplification in proof complexity. In Proceedings of the 42nd ACM Symp. on Theory of Computing, STOC 2010. Schulman, L.J. (ed), ACM, NY, (2010), 8796.
    • 3. Bürgisser, P.  Cook's versus valiant's hypothesis. Theor. Comput. Sci. 235, 1 (2000), 7188.
    • 4. Bürgisser, P. et al.  Algebraic Complexity Theory, volume 315 of Grundlehren der Mathematischen Wissenschaften. Springer, Berlin, Heidelberg (1997); DOI: 10.1007/978-3-662-03338-8.
    • 5. Chou, C.-N. et al.  Closure results for polynomial factorization. Theory Comput. 15, Paper No. 13, 34 (2019).
    • 6. Dvir, Z. et al.  Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. Comput. 39, 4 (2009), 12791293.
    • 7. Fournier, H. et al.  Lower bounds for depth-4 formulas computing iterated matrix multiplication. SIAM J. Comput. 44, 5 (2015), 11731201.
    • 8. Gupta, A. et al.  Approaching the chasm at depth four. J. ACM. 61, 6 (Dec. 2014), 33:133:16.
    • 9. Gupta, A. et al.  Arithmetic circuits: A chasm at depth 3. SIAM J. Comput. 45, 3 (2016), 10641079.
    • 10. Hrubeš, P., and Yehudayoff, A.  Homogeneous formulas and symmetric polynomials. Comput. Complexity. 20, 3 (2011), 559578.
    • 11. Kabanets, V., and Impagliazzo, R.  Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complexity. 13, 1–2 (2004), 146.
    • 12. Koiran, P.  Arithmetic circuits: The chasm at depth four gets wider. Theor. Comput. Sci. 448, (2012), 5665.
    • 13. Kumar, M., and Saptharishi, R.  Hardness-randomness tradeoffs for algebraic computation. Bull. EATCS. 129, (2019).
    • 14. Kumar, M., and Saraf, S. On the power of homogeneous depth 4 arithmetic circuits. SIAM J. Comput. 46, 1 (2017), 336387.
    • 15. Nisan, N., and Wigderson, A. Lower bounds on arithmetic circuits via partial derivatives. Comput. Complexity. 6, 3 (1997), 217234.
    • 16. Raz, R. Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM. 56, 2 (2009), 8:18:17.
    • 17. Raz, R. Elusive functions and lower bounds for arithmetic circuits. Theory Comput. 6, 1 (2010), 135177.
    • 18. Raz, R. Tensor-rank and lower bounds for arithmetic formulas. J. ACM. 60, 6 (2013), 40:140:15.
    • 19. Saptharishi, R. A survey of lower bounds in arithmetic circuit complexity. Github survey, (2015).
    • 20. Saxena, N.  Progress on polynomial identity testing. Bull. EATCS. 99, (2009), 4979.
    • 21. Shpilka, A., and Wigderson, A.  Depth-3 arithmetic circuits over fields of characteristic zero. Comput. Complexity. 10, 1 (2001), 127.
    • 22. Shpilka, A., and Yehudayoff, A.  Arithmetic circuits: A survey of recent results and open questions. Found. Trends Theor. Comput. Sci. 5, (Mar2010), 207388.
    • 23. Strassen, V.  Vermeidung von divisionen. J. für die reine und angewandte Mathematik. 264, (1973), 184202.
    • 24. Tavenas, S.  Improved bounds for reduction to depth 4 and depth 3. Inf. Comput. 240, (2015), 211.
    • 25. Valiant, L.G.  Completeness classes in algebra. In Proceedings of the 11th Annual ACM Symp. on Theory of Computing, April 30–May 2, 1979, Atlanta, Georgia, USA. Fischer, M.J. et al. (eds). ACM, NY (1979), 249261.
    • One can also consider divisions, but they can typically be eliminated without much extra cost.
    • We typically consider an infinite sequence of polynomials, a distinction that we frequently gloss over in this paper. We also require that the polynomials have only moderate degree, that is, that the degree grows at most as a polynomial function in the number of input variables. A good example to keep in mind is the problem of computing the determinant of an n × n matrix. This gives, for each n, a multivariate polynomial of degree n in N = n2 variables.
    • The random point is typically picked uniformly at random from a large finite grid of points.
    • This terminology appeared in a result of Beame et al.2 on proof complexity. The authors of that paper attribute the term to Rahul Santhanam.
    • Raz's result is slightly stronger for homogeneous formulas, but we ignore this point here.
    • A formula is called a fanin-2 formula, if every gate has at most 2 input wires.
    • In fact, they claim the result for general depth-4 circuits, but it was already noticed in Gupta et al.9 that the formula they get with this approach is homogeneous. In fact in Gupta et al.9 they also show that the product gates can be replaced by exponentiation gates, but we do not need it here.

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More