Home/Magazine Archive/February 2024 (Vol. 67, No. 2)/Superpolynomial Lower Bounds Against Low-Depth Algebraic.../Full Text

Research Highlights
## Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

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.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 book^{4} or the surveys.^{13,19,20,22} Here, we study algebraic problems that are closely related to multivariate polynomials over some fields F which we will assume to be the complex numbers C in this paper. An example of such a polynomial in 3 variables of degree 3 is

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}

**Figure 1. 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 = n*^{2} 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 *N ^{d}.*

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 ΣΠ. For instance, the polynomial from Equation (1) can be written more succinctly as

which can be seen as a simple ΣΠΣ circuit. More generally, a surprising and beautiful result of Gupta et al.^{9} (building on many previous results^{1,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 . While this is quite large, it is still considerably smaller than the trivial *N ^{d}* 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 P _{N,d}* (

In the case of ΣΠΣ circuits (i.e., Δ = 3), we get a lower bound of . 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 *P _{N,d}* itself is easy to describe and encodes the natural problem of Matrix Multiplication. Assume

**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 nonzero 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 surveys^{13,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 Impagliazzo^{11} 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*^{Δ+1}·*n*)^{O(nε)}.

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*(*x*_{1}, …, *x _{N}*) is one in which each variable

Given a set-multilinear polynomial *P* (w.r.t. variable partition *X*_{1}, …, *X _{d}*), it is natural to look at algebraic circuits computing

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. Strassen^{23} and Raz^{17} 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, Raz^{18} 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

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 IMM_{n,d} polynomial on *N* = *dn*^{2} variables as defined above. This polynomial has a simple divide-and-conquer-based set-multilinear formula of size *n*^{O(log d)}, and more generally for every Δ ≤ log *d*, a set-multilinear formula of depth 2Δ and size *n*^{O(Δ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* IMM* _{n,d} of depth at most* Δ

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 · d*^{O(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* IMM* _{n,d} of depth at most* Δ

Note that our improved non-FPT bounds are crucial for deriving the above result from Theorem 3. The previous best lower bound of due to Nisan and Wigderson^{15} does not suffce for this, because of the *d*^{O(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 poly(*s*) · .

This implies the main result Theorem 1.

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).

Raz^{18} showed that if there is a fanin-2 formula of size *s* and depth Δ that computes a set-multilinear polynomial over the disjoint sets (*X*_{1}, …, *X _{d}*), then there exists also a fanin-2 set-multilinear formula of size

We show here that we can get a similar result for circuits with arbitrary fanins at the cost of a size blow-up of *d*^{O(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 s* ≥ *Nd. 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* (*X*_{1}, …, *X _{d}*)

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 noticed^{9,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

where each *ℓ*_{i,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*) · . 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 poly(*s*) · .^{f}

The main observation is also easy to prove. Consider any summand *T _{t}* =

where each is a homogeneous linear polynomial. It then follows that the degree-*d* homogeneous part *T _{i,d}* of

Shpilka and Wigderson^{21} [Theorem 5.3] proved that, over fields of characteristic 0 the polynomial has a homogeneous ΣΠΣΠ circuit of size poly(s) · . 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*(*x*_{1}, *…, x _{N}*)

**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 s* ≥ *Nd. 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* (*X*_{1}, …, *X _{d}) (with |X_{i}*| ≤

PROOF. Let us describe our new circuit . For any gate *α* of degree *d _{α}* from

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

If *α = c*^{1}*α*^{1} + … + *c*^{p}*α*^{p} is a sum gate (where the *c ^{i}* are constants in ℂ), we just need to compute the linear combination part by part. For any

Finally, if *α = α*^{1} … *α ^{p}* is a product gate, we need to extract all the decompositions. Let

The size of the sum is

Hence each leaf and sum gate *α* in *C* creates new gates in . Each multiplication gate *α* in *C* creates sum gates and new product gates. So the number of gates of *C* is bounded by 2*d*! 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 is the same as the one of the gate

**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} *with* . *Any set-multilinear circuit C of depth* 5 *computing* IMM_{n,d} *has size at least* .

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 *d*^{O(d)}poly(*s*). By Lemma 8, it implies that . 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 Wigderson^{15}) 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 = (w_{1}, …, w_{d})**∊

Given *w*, we denote by a tuple of *d* sets of variables (*X(w*_{1}), …, *X*(*w _{d}*)) where |

Let and denote the sets of the set-multilinear monomials over only the positive and only the negative variable sets. Let , we define *M _{w}(f)* as the matrix of size , where the rows are indexed by and the columns by and where the coefficient at the entry

We associate with the space the standard rank-based complexity measure relrk_{w} (short for "relative rank") defined as follows. Let and define

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 relrk_{w.}

CLAIM 9.

*(Imbalance) Say*.*Then*, relrk_{w}, (*f*) ≤ 22^{−|w[d]|/2}.*(Sub-additivity) Say*.*Then*relrk_{w}(*f*+*g*) ≤ relrk_{w}(*f*) + relrk_{w}(*g*).*(Multiplicativity) Say f = f*_{1}*f*_{2}…*f*,_{t}and assume that for each*where*(*S*_{1}, …,*S*[_{t}) is a partition of*d*]*and for each**i*∈[*t*],*w*_{|Si}*stands for the sub-word of w indexed by S*_{i}. Then

PROOF. We have that and . So _{2}^{|w[d]|} is just the ratio of the larger dimension of *M _{w}*(

The subadditivity property directly follows from the facts that *M _{w}*(

The multiplicative argument is standard too. As the product is set-multilinear, it implies that the matrix *M _{w}*(

**Word polynomials and iterated matrix multiplication polynomial.** We said we will prove lower bounds for lopsided polynomials. Unfortunately, all variables parts of the polynomial IMM_{n,d} have the same size (which is *n ^{2})*. In fact, we will prove the lower bound for the word polynomial which is a "set-multilinear" projection of IMM

Let ** w** ∊

Given any monomial , let *m*_{+} denote the corresponding "positive" monomial from and *m*_{-} the corresponding "negative" monomial from . As each variable of is labeled by a Boolean string and each set-multilinear monomial over any subset of is associated with a string of variables, we can associate any such monomial ** m**′ with a Boolean string

The polynomial *P _{w}* is defined as follows:

Clearly, the matrices *M _{w}*(

We observe that *P _{w}* can be obtained as a

LEMMA 10. *Let w* ∊

**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* *be an integer. Let w be any word of length d on the alphabet* . *Then any set-multilinear formula C of depth* 5 *and of size s satisfies*

Indeed, by fixing ** k** = ⌊

for the polynomial **IMM**_{2k,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 = C*_{1} + … *+ C _{t}* where each

- If
*C*is of type 1, then_{i}*C*=_{i}*C*_{i,1}·…·*C*_{i,ti}. Up to reordering, we can assume that*C*is a sum of products of linear forms of degree at least . Notice that if_{i,1}*L*is a linear form on variables*X*(*w*), we have . In particular, by the multiplicativity and sub-additivity of relrk_{i}_{w}(Claim 9),

- If
*C*is of type 2, then_{i}*C*=_{i}*C*_{i,1}·…·*C*_{i,ti}where each factor*C*has degree . Each_{ij}*C*is a set-multilinear formula over a subset_{ij}**(**:*X*(*w*_{p})*p*∊*S*) for some_{j}*S*⊆ [_{j}*d*], where*S*_{1}, …,*S*_{ti}partition [*d*]. Let*w*^{iti}be the corresponding decomposition of*w.*That is,*w*^{ij}=*w*_{|Sj}. Recall that or a word*w*we defined in the preliminaries as the sum of its entries.^{ij}

Let*j*∊[*t*]. Let_{i}*a*be the number of positive indices in_{ij}*w*If^{ij}.*2a*deg(_{ij}≤*C*), then_{i,j}

- Otherwise, we have

- So in both cases, .

In particular,

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

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 s ≥ N. If C is a circuit of size at most s and depth at most* ∆ *computing a homogeneous polynomial P(x _{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 *C _{i}* is of type 2 in the proof can be tackled. Then the first case (

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 ≥* 2^{10d+1}. *Any set-multilinear circuit C of depth* ∆ *computing* IMM_{n,d} *has size at least*

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.

1. Agrawal, M., Vinay, V. Arithmetic circuits: A chasm at depth four. In *Proceedings of Foundations of Computer Science (FOCS)*, USA (2008), 67–75. DOI: 10.1109/FOCS.2008.32.

2. Beame, P., Huynh, T., Pitassi, T. Hardness amplification in proof complexity. In *Proceedings of the 42 ^{nd} ACM Symposium on Theory of Computing, STOC 2010.* L.J. Schulman, ed. ACM, NY, 2010, 87–96.

3. Bürgisser, P. Cook's versus valiant's hypothesis. *Theor. Comput. Sci. 235*, 1 (2000), 71–88.

4. Bürgisser, P., Clausen, M., Shokrollahi, M.A. *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., Kumar, M., Solomon, N. Closure results for polynomial factorization. *Theory Comput.* 15: Paper No. 13, 34 (2019).

6. Dvir, Z., Shpilka, A., Yehudayoff, A. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. *SIAM J. Comput. 39*, 4 (2009), 1279–1293.

7. Fournier, H., Limaye, N., Malod, G., Srinivasan, S. Lower bounds for depth-4 formulas computing iterated matrix multiplication. *SIAM J. Comput. 44*, 5 (2015), 1173–1201.

8. Gupta, A., Kamath, P., Kayal, N., Saptharishi, R. Approaching the chasm at depth four. *J. ACM 61*, 6 (Dec. 2014), 33:1–33:16.

9. Gupta, A., Kamath, P., Kayal, N., Saptharishi, R. Arithmetic circuits: A chasm at depth 3. *SIAM J. Comput. 45*, 3 (2016), 1064–1079.

10. Hrubeš, P., Yehudayoff, A. Homogeneous formulas and symmetric polynomials. *Comput. Complexity 20*, 3 (2011), 559–578.

11. Kabanets, V., Impagliazzo, R. Derandomizing polynomial identity tests means proving circuit lower bounds. *Comput. Complexity 13*, 1–2 (2004), 1–46.

12. Koiran, P. Arithmetic circuits: The chasm at depth four gets wider. *Theor. Comput. Sci. 448* (2012), 56–65.

13. Kumar, M., Saptharishi, R. Hardness-randomness tradeoffs for algebraic computation. *Bull. EATCS 129* (2019).

14. Kumar, M., Saraf, S. On the power of homogeneous depth 4 arithmetic circuits. *SIAM J. Comput. 46*, 1 (2017), 336–387.

15. Nisan, N., Wigderson, A. Lower bounds on arithmetic circuits via partial derivatives. *Comput. Complexity 6*, 3 (1997), 217–234.

16. Raz, R. Multi-linear formulas for permanent and determinant are of super-polynomial size. *J. ACM 56*, 2 (2009), 8:1–8:17.

17. Raz, R. Elusive functions and lower bounds for arithmetic circuits. *Theory Comput. 6*, 1 (2010), 135–177.

18. Raz, R. Tensor-rank and lower bounds for arithmetic formulas. *J. ACM 60*, 6 (2013), 40:1–40: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), 49–79.

21. Shpilka, A., Wigderson, A. Depth-3 arithmetic circuits over fields of characteristic zero. *Comput. Complexity 10*, 1 (2001), 1–27.

22. Shpilka, A., Yehudayoff, A. Arithmetic circuits: A survey of recent results and open questions. *Found. Trends Theor. Comput. Sci. 5* (Mar 2010), 207–388.

23. Strassen, V. Vermeidung von divisionen. *J. für die reine und angewandte Mathematik 264* (1973), 184–202.

24. Tavenas, S. Improved bounds for reduction to depth 4 and depth 3. *Inf. Comput. 240* (2015), 2–11.

25. Valiant, L.G. Completeness classes in algebra. In *Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30–May 2, 1979, Atlanta, Georgia, USA.* M.J. Fischer, R.A. DeMillo, N.A. Lynch, W.A. Burkhard, A.V. Aho, eds. ACM, NY, 1979, 249–261.

a. One can also consider divisions, but they can typically be eliminated without much extra cost.

b. 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* = *n*^{2} variables.

c. The random point is typically picked uniformly at random from a large finite grid of points.

d. 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.

e. Raz's result is slightly stronger for homogeneous formulas, but we ignore this point here.

f. A formula is called a fanin-2 formula, if every gate has at most 2 input wires.

g. 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.

To view the accompanying Technical Perspective, visit doi.acm.org/10.1145/3631338

The original version of this paper was published in the *Proceedings of the 2021 IEEE 62 ^{nd} Annual Symposium on Foundations of Computer Science*, Denver, CO, USA.

© 2024 Copyright held by the owner/author(s). Publication rights licensed to ACM.

Request permission to publish from permissions@acm.org

The Digital Library is published by the Association for Computing Machinery. Copyright © 2024 ACM, Inc.

No entries found