Nutan Limaye

Srikanth Srinivasan

Sébastien Tavenas

New Non-FPT Lower Bounds for Some Arithmetic Formulas

An Algebraic Formula for a polynomial P P Frx 1 , . . . , x N s is an algebraic expression for P px 1 , . . . , x N q using variables, field constants, additions and multiplications. Such formulas capture an algebraic analog of the Boolean complexity class NC 1 . Proving lower bounds against this model is thus an important problem.

 the first non-FPT lower bounds, i.e., a lower bound of the form N Ωpf pdqq , against small-depth set-multilinear formulas (and also for circuits). In this work, we extend this result in two directions.

1. Large-depth set-multilinear formulas. In the setting of general set-multilinear formulas, we prove a lower bound of plog nq Ωplog dq for computing the Iterated Matrix Multiplication polynomial IMM n,d . In particular, this implies the first superpolynomial lower bound against unbounded-depth set-multilinear formulas computing IMM n,n .

As a corollary, this also resolves the homogeneous version of a question of Nisan (STOC 1991) regarding the relative power of Algebraic formulas and Branching programs in the non-commutative setting.

2. Stronger bounds for homogeneous non-commutative small-depth circuits.

In the small-depth homogeneous non-commutative case, we prove a lower bound of n d 1{∆ {2 Op∆q , which yields non-FPT bounds for depths up to op ? log dq. In comparison, the bound in [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF] works in the harder commutative set-multilinear setting, but only up to depths oplog log dq. Moreover, our lower bound holds for all values of d, as opposed to the set-multilinear lower bound of [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF], which holds as long as d is small, i.e., d " Oplog nq.

Introduction

Polynomials and Algebraic Formulas. Let P px 1 , . . . , x N q be a polynomial over a field F. An Algebraic Formula computing a polynomial P px 1 , . . . , x N q is a directed tree in which the leaves are labelled by variables from X " tx 1 , . . . , x N u or field constants and the internal nodes are labelled by addition or multiplication operators. If an internal node is labelled by the addition operator, then it computes a linear combination of its inputs. Similarly, if it is labelled by the multiplication operator, then it computes the product of its inputs 1 . The size of the formula is the number of nodes in the tree. The product-depth of the formula is the largest number of multiplication gates along any root-to-leaf path.

The class of polynomials that have algebraic formulas of polynomial size is denoted VP e and is an algebraic analog of the Boolean complexity class NC 1 . Proving lower bounds for this class is therefore an important problem in complexity theory in general, and in particular for Algebraic Complexity theory, which is the study of the computational complexity of algebraic problems of this kind (see, e.g. [START_REF] Bürgisser | Algebraic complexity theory[END_REF][START_REF] Shpilka | Arithmetic circuits: A survey of recent results and open questions[END_REF][START_REF] Saptharishi | A survey of lower bounds in arithmetic circuit complexity[END_REF] for nice introductions to this area). The problem has been investigated for many years and we have several lower bounds against many restricted classes of formulas [START_REF] Brent | The parallel evaluation of general arithmetic expressions[END_REF][START_REF] Kalorkoti | A lower bound for the formula size of rational functions[END_REF][START_REF] Nisan | Lower bounds on arithmetic circuits via partial derivatives[END_REF][START_REF] Raz | Multi-linear formulas for permanent and determinant are of super-polynomial size[END_REF][START_REF] Dvir | Separating multilinear branching programs and formulas[END_REF][START_REF] Gupta | Approaching the chasm at depth four[END_REF][START_REF] Kayal | An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits[END_REF][START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF].

Set-multilinear formula lower bounds. Recall that a polynomial P px 1 , . . . , x N q is homogeneous if each monomial has the same total degree. It is multilinear if every variable occurs at most once in any monomial. Suppose the underlying variable set is partitioned into d sets, X 1 , . . . , X d , then the polynomial is set-multilinear with respect to this variable partition if each monomial in P has exactly one variable from each set.

Many interesting and well-studied polynomials are set-multilinear. For example, the Determinant and the Permanent polynomials, which are central to algebraic complexity theory, are set-multilinear (w.r.t. the row variables). Another well-studied polynomial, namely the Iterated Matrix Multiplication polynomial, is also set-multilinear. As we will use this polynomial in what comes next, we recall the definition. The Iterated Matrix Multiplication polynomial IMM n,d is defined on N " dn 2 variables, where the variables are partitioned into d sets X 1 , . . . , X d of size n 2 , each of which is represented as an n ˆn matrix with distinct variable entries. The polynomial IMM n,d is defined to be the polynomial that is the p1, 1qth entry of the product matrix X 1 ¨X2 ¨¨¨X d .

Corresponding to the above variants of polynomials classes, we also define different models of computation. An algebraic formula is set-multilinear with respect to a variable partition pX 1 , . . . , X d q if each internal node in the formula computes a set-multilinear polynomial. Similarly, we define homogeneous formulas and multilinear formulas.

We have several interesting lower bound results against set-multilinear formulas. Nisan and Wigderson [START_REF] Nisan | Lower bounds on arithmetic circuits via partial derivatives[END_REF] proved the first exponential lower bound for product-depth 1 set-multilinear formulas. In particular, among other results, they proved that any product-depth 1 set-multilinear formula computing IMM n,d must have size n Ωpdq . They introduced the partial derivative technique to prove this lower bound. Building on this technique, Raz [START_REF] Raz | Multi-linear formulas for permanent and determinant are of super-polynomial size[END_REF] showed the first superpolynomial lower bound on the size of any arbitrary depth multilinear formula (of arbitrary depth) computing the n ˆn Determinant and Permanent. In follow-up works [START_REF] Raz | Separation of multilinear circuit and formula size[END_REF][START_REF] Dvir | Separating multilinear branching programs and formulas[END_REF] other candidate multilinear polynomials, of varying complexity, were shown to be hard for arbitrary depth polynomial sized multilinear formulas.

Given the large array of lower bounds for restricted models of computation and lack thereof for general formulas, the following question arises naturally. Can we use the known lower bounds for restricted classes of formulas to obtain lower bounds for general formulas? An intriguing observation of Raz [START_REF] Raz | Tensor-rank and lower bounds for arithmetic formulas[END_REF] suggests a way. Raz showed that if a set-multilinear polynomial of degree d has an algebraic formula of size s, then it also has a set-multilinear formula of size polypsq ¨plog sq Opdq . In particular, for a set-multilinear polynomial P of degree d " Oplog N { log log N q, it follows that P has a formula of size polypN q if and only if P has a set-multilinear formula of size polypN q.

This offers us a possible route towards proving general algebraic formula lower bounds via 'hardness escalation' from the set-multilinear case. It is not hard to show that a random polynomial of degree d in N variables has no formulas of size N opdq . If we could prove such a lower bound against set-multilinear formulas for computing an explicit polynomial of small degree d, then we would be done.

Non-FPT lower bounds. On the one hand, we have several lower bounds for set-multilinear formulas and on the other hand we have the hardness escalation result by Raz. The missing piece of the puzzle has been the quality of the lower bound needed for making escalation possible. Specifically, all the lower bounds known for arbitrary depth set-multilinear formulas are of the form Ωpf pdq polypN qq (where f is typically a superpolynomial but at best exponential function). Using an analogy to Parameterized Complexity Theory [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF], we call such bounds FPT bounds. However, we would like to prove N ω d p1q lower bounds. We call such bounds non-FPT bounds.

While we do not have non-FPT bounds for general set-multilinear formulas, we have such bounds in the small product-depth setting. The result by Nisan and Wigderson, mentioned above, is the first example of such a bound. Recently, the authors generalised that result [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF] and obtained non-FPT bounds for all constant product-depth formulas (and also for circuits) 2 . This result also gave interesting consequences. Specifically, it gave the first superpolynomial lower bounds against all constant depth formulas.

Our Results. In this work, we take a step towards proving non-FPT lower bounds for arbitrary depth set-multilinear formulas. Specifically, we prove the following theorem.

Theorem 1. Let n, d, ∆ be growing parameters with ∆ ď Oplog dq. Then any set-multilinear formula of product-depth at most ∆ for IMM n,d must have size at least plog nq Ωp∆d 1{∆ q . Further, any set-multilinear formula for IMM n,d must have size at least plog nq Ωplog dq .

To put the above result in context, this improves the above mentioned result of Nisan and Wigderson, who proved a lower bound of exppΩpd 1{∆ qq, which can be improved to exppΩp∆d 1{∆ qq with a slightly more careful analysis. On the other hand, the standard divide-and-conquer strategy for constructing formulas for IMM n,d yields an upper bound of n Op∆d 1{∆ q . If we conjecture that this is tight, then we expect to change the base of the exponent in the lower bound to be n. Our result seems to be the first to achieve any dependence on n.

The above result also extends the results from [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF] in two ways.

• It gives a lower bound for IMM n,d against formulas of any depth. The result in [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF] works for depths up to Oplog log dq.

• It puts no restriction on the degree of the polynomial. The lower bound in [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF] essentially works for degree d " Oplog nq. 3In the case that d " n Ωp1q , we get a superpolynomial bound of n Ωplog log nq for set-multilinear formulas computing IMM n,d . Corollary 2. Any set-multilinear formula computing IMM n,n must have size at least n Ωplog log nq .

Notice that Raz's escalation result is only useful when we have a non-FPT lower bound for d " Oplog N { log log N q. But for small d (say d ď plog nq Op1q ), our result yields a bound of less than n, which is trivial. This may indicate that the above is not really useful from a hardness escalation perspective.

However, we observe that there is an interesting connection. Here, notice that our lower bound is for IMM n,n , which is a self-reducible polynomial. In this context, this refers to the fact that we can construct formulas for IMM n,n by recursively using formulas for IMM n,d (for any d ă n). In particular, if we had formulas of size n oplog dq for IMM n,d , this would imply formulas of size n oplog nq for IMM n,n . Stated in the contrapositive, this means that an optimal n Ωplog nq lower bound for IMM n,n implies non-FPT lower bounds for d ă n, which would then imply general formula lower bounds via escalation. Our superpolynomial lower bound makes the first non-trivial progress towards this goal for unbounded depth set-multilinear formulas (but see also Related work below).

The above corollary also implies an interesting result for Non-commutative Algebraic Formulas. A non-commutative algebraic formula is defined just as a standard algebraic formula, except that the underlying variables do not commute. 4 In this setting, explicit superpolynomial formula lower bounds (and also non-FPT lower bounds) follow easily from work of Nisan [START_REF] Nisan | Lower bounds for non-commutative computation[END_REF]. However, it is still interesting to prove a superpolynomial lower bound against non-commutative formulas computing IMM n,d , as this would separate VBP and VP e in the non-commutative setting, which would solve an open question due to Nisan [START_REF] Nisan | Lower bounds for non-commutative computation[END_REF]. Our result, along with the fact that non-commutative homogeneous formulas yield set-multilinear formulas (see Lemma 6), implies that we have resolved Nisan's question for homogeneous formulas. As mentioned above, the standard divide-and-conquer strategy gives set-mulilinear formulas of product-depth ∆ and size n Op∆d 1{∆ q computing IMM n,d . This means that we can potentially prove a lower bound of n Ωp∆d 1{∆ q in this setting. Unfortunately, we do not know how to prove this kind of bound even for product-depth three 5 .

Here, we prove such a lower bound in the case of non-commutative homogeneous constantdepth formulas. Specifically, we prove the following theorem. Theorem 4. Let n, d be any growing parameters. Any constant product-depth ∆ non-commutative homogeneous formulas for IMM n,d must have size n Ωpd 1{∆ q . Further, if ∆ is any growing parameter, then any product-depth ∆ non-commutative homogeneous circuit for IMM n,d must have size at least n d 1{∆ {2 Op∆q .

As any circuit of product-depth ∆ and size s can be converted into a formula of product-depth ∆ and size s Op∆q , the same lower bounds continue to hold for homogeneous non-commutative circuits.

Note that, this gives a non-FPT lower bounds for product-depths all the way to Op ? log dq. Moreover, we can also easily compute such polynomials if we consider formulas of product-depth ∆ `1 (instead of ∆). It implies an exponential separation between non-commutative formulas of different product-depth (see Corollary 17).

Related Work. We have set-multilinear formula lower bounds for unbounded-depth formulas since the early 2000s. Raz [START_REF] Raz | Multi-linear formulas for permanent and determinant are of super-polynomial size[END_REF] showed an n Ωplog nq lower bound on the size of any multilinear (and hence in particular set-multilinear) formula for the Determinant, and Dvir, Malod, Perifel and Yehudayoff [START_REF] Dvir | Separating multilinear branching programs and formulas[END_REF] prove similar lower bounds for another multilinear polynomial on n variables. Unfortunately, these polynomials are not self-reducible in the same sense as IMM is (as sketched above) and so it is unclear if we can use these bounds to obtain non-FPT lower bounds.

However, both these families of polynomials lie in the complexity class VBP. Given that IMM n,n is complete for this class, one might expect that we get a similar lower bound for this polynomial. Curiously, however, these results do not imply any lower bound for IMM n,n . This is because the underlying reductions to IMM n,n destroy the multilinearity of the formula, and hence the multilinear formula lower bounds no longer apply. Therefore, as far as we know, despite this progress, we did not have any unbounded-depth formula lower bounds for IMM n,n , even in the set-multilinear setting, prior to this work.

Nisan and Wigderson [START_REF] Nisan | Lower bounds on arithmetic circuits via partial derivatives[END_REF] proved a non-FPT bound for a special kind of commutative setmultilinear formulas called pure circuits 6 . More recently, Chatterjee [START_REF] Chatterjee | Separating abps and some structured formulas in the non-commutative setting[END_REF] also proved a non-FPT bound for another variety of restricted non-commutative formulas, called Abecedarian formulas. Theorem 4 above strengthens the first result. 7 However, it seems incomparable to the second result, as the lower bound result of [START_REF] Chatterjee | Separating abps and some structured formulas in the non-commutative setting[END_REF] is for a non-set-multilinear polynomial. At a higher level, our techniques are also quite different, as we use rank-based arguments, while Chatterjee's lower bound uses a result of Hrubeš and Yehudayoff [START_REF] Hrubeš | Homogeneous formulas and symmetric polynomials[END_REF] that uses the sparsity (number of monomials) in the underlying polynomial. Such a technique does not seem to be applicable in our setting.

Our Techniques. At a high level, the proof outline for our lower bound in Theorem 1 looks very similar to that of many known lower bounds. We design a measure µp¨q on the space of polynomials such that the measure is small for all the polynomials computed by set-multilinear formulas, whereas it is large for the IMM polynomial.

Nisan and Wigderson defined the partial derivative measure and used it to prove the first non-FPT lower bound for product-depth 1 set-multilinear formulas, which we mentioned earlier.

The measure has been extended in many ways over the years to obtain many strong lower bounds (see for instance [START_REF] Raz | Separation of multilinear circuit and formula size[END_REF][START_REF] Shpilka | Depth-3 arithmetic circuits over fields of characteristic zero[END_REF][START_REF] Kayal | An exponential lower bound for the sum of powers of bounded degree polynomials[END_REF][START_REF] Gupta | Approaching the chasm at depth four[END_REF][START_REF] Kayal | An exponential lower bound for homogeneous depth four arithmetic formulas[END_REF]).

We describe the measure here, as it will help in the proof outline. Let P, N be a partition of rds. The variable sets pX 1 , . . . , X d q are partitioned as positive variables pX i : i P Pq and negative variable pX i : i P N q. Let us fix this variable partition. Let M P be the set of monomials over positive variables and let M N be the set of monomials over negative variables. Given a setmultilinear polynomial f over pX 1 , . . . , X d q, we define a matrix M f to be a matrix whose rows are labelled by M P and columns are labelled by M N . For m 1 P M P and m 2 P M N , the pm 1 , m 2 qth entry is the coefficient of m 1 ¨m2 in f . The measure is defined as the rank of M f . 8 .

The non-commutative homogeneous case. Theorem 4 strengthens the lower bound proved in [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF] in the non-commutative homogeneous setting. At a conceptual level, the proof of Theorem 4 is similar to the proof of the lower bound in [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF]. To describe the key idea, we briefly recall the proof idea from [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF].

The proof in [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF] proceeds along similar lines as the high level proof idea described above. The complexity measure used in [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF] is the partial derivative measure, the same as in [START_REF] Nisan | Lower bounds on arithmetic circuits via partial derivatives[END_REF].

In Nisan and Wigderson, |X i | " |X j | for all i ‰ j P rds, that is, they defined the hard polynomial over a variable partition where each set had the same size. The lower bound proof in [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF] deviates from this and chooses the set sizes carefully. All the positive sets are of the same size, i.e. |X i | " |X j | " m for all i ‰ j P P, and all the negative sets are of the same size, i.e. |X i | " |X j | " m 1 . for all i ‰ j P N , but m ‰ m 1 . In fact, m 1 is m 1´δ for a carefully chosen δ.

This measure is then analysed for set-multinear formulas. Suppose F " F 1 ¨F2 ¨. . . ¨Fr is a specific product gate in the formula. We consider two cases. The first case is that, one of the F i s has large degree. In this case, the argument proceeds inductively by bounding the measure for a sub-formula inside F i with one less product-depth.

The other case is that all the F i s have small degrees. The careful choice of set sizes helps in bounding the measure for factors with small degree (say degree equal to Op1{δq). We can observe that, as the degree of F i is small, no matter how F i uses the subsets of positive and negative variables, the matrix M F i 9 will have fewer columns than rows, thereby causing some rank deficiency. For a term F in which all factors have small degrees, we thus obtain rank deficiency from each factor.

Here, for the non-commutative homogeneous lower bound, we use a similar proof idea. The main difference is how we analyse the measure for non-commutative homogeneous formulas. In the set-multilinear case each sub-formula depended on variable sets pX i : i P Jq, where J Ď rds. Whereas here, each sub-formula depends on a subset of variable sets pX i : i P Jq, such that J is an interval. It turns out that we can leverage this difference and quantitatively improve the lower bounds.

The large depth case. To get lower bounds for set-multilinear formulas of product-depths greater than 1, Nisan and Wigderson combined the partial derivative measure with the method of random restrictions. A restriction ρ is a function that sets some of the variables to field constants. It is a random restriction if this map is random. (The choice of the distribution can play a key role in the proof.) They were able to show that the hard polynomial (say e.g. IMM) continues to have a high measure even after being subject to a restriction, while the measure for the set-multilinear formulas drops further under the random restriction with high probability. Using this, they proved an FPT lower bound of polypnq ¨exppΩpd 1{∆ qq for product-depth ∆ ą 1.

In their proof, for the sets of variables X 1 , . . . , X d , they choose a random subset I Ď rds and then set all the variables in Y jRI X j to constants. It is not very hard to see that their choice of random restriction cannot give non-FPT lower bounds. Intuitively, this is because there are at most 2 d choices for I.

In our proof, instead of setting all the variables from a set to constants, we choose a (random) subset of variables inside each X i and set those variables to constants. It is easy to see that in our setting, we have up to n Ωpdq many choices for the random restriction. Intuitively, this may be the reason why we are able to get a non-FPT lower bound.

Preliminaries

We will consider the set of words on an alphabet A Ď Z. Let w " pw 1 , . . . , w d q P A d . For an interval I Ď rds, let |w I | denote ř iPI w i . We define P w " ti | w i ě 0u and N w " ti | w i ă 0u, i.e., the positive and negative indices of w respectively.

We say w is balanced if |w rds | " 0 and k-unbiased if |w rts | ď k for t ď d.

Given w, we denote by Xpwq a tuple of d sets of variables pXpw 1 q, . . . , Xpw d qq where

|Xpw i q| " 2 |w i | .
We denote by F sm rT s the set of set-multilinear polynomials over the tuple of sets of variables T . Similarly we denote by F sm xT y the set of non-commutative set-multilinear polynomials over the tuple T (i.e., more formally, F sm xT y is the set of non-commutative polynomials that are linear combination of monomials where each monomial is of the form x 1 ¨¨¨x d with x i P T i ).

Notice that since T " pT 1 , . . . , T d q is chosen ordered, there is a natural bijection between F sm rT s and F sm xT y. Indeed, let π : F sm xT y Ñ F sm rT s be the usual projection we got by forgetting the order of the monomials. Then, given any monomial m P F sm rT s, we know there is a permutation σ such that m i P T σ ´1piq for all i. It implies that π ´1pmq " m σp1q . . . m σpdq . So, in the set-multilinear case, π is one-to-one.

The complexity measure

Let M P w and M N w denote the sets of the set-multilinear monomials over only the positive and only the negative variable sets. Let f P F sm rXpwqs, we define M w pf q as the matrix of size

|M P w | ˆ|M N w |
, where the rows are indexed by M P w and the columns by M N w and where the coefficient at the entry pm 1 , m 2 q corresponds to the coefficient of the monomial m 1 m 2 in f .

We associate with the space F sm rXpwqs the standard rank-based complexity measure relrk w (short for "relative rank") defined as follows. Let f P F sm rXpwqs and define relrk w pf q " rankpM w pf qq

a |M P w | ¨|M N w | " rankpM w pf qq 2 1 2 ř iPrds |w i | ď 1.
We use the following properties of relrk w . The (standard) proof can be found in [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF].

Claim 5.

1. (Imbalance) Say f P F sm rXpwqs. Then, relrk w pf q ď 2 ´|w rds |{2 .

2. (Sub-additivity) Say f, g P F sm rXpwqs. Then relrk w pf `gq ď relrk w pf q `relrk w pgq.

3. (Multiplicativity) Say w " w 1 w 2 (i.e., w is the concatenation of w 1 and w 2 ). Assume f i P F sm rXpw i qs (i P r2s). Then relrk w pf 1 ¨f2 q " relrk w 1 pf 1 q ¨relrk w 2 pf 2 q.

If f is non-commutative, i.e., if f P F sm xXpwqy, then we define relrk w pf q " relrk w pπpf qq.

We can easily notice that the three assertions of Claim 5 still hold in the non-commutative settings since π is additive and multiplicative.

Non-commutative algebraic models of computation

We recall some definitions and facts about non-commutative algebraic models of computation (see, e.g. [START_REF] Nisan | Lower bounds for non-commutative computation[END_REF]).

Fix a variable set X and an ordered variable partition pX 1 , . . . , X d q.

A non-commutative algebraic formula F over X is a directed tree where leaves are labelled by variables and elements of the field F, and internal nodes are labelled by `and ˆ. Each gate in F computes a polynomial in the non-commutative ring FxXy. Gates labelled `compute a linear combination of their inputs (where the coefficients of the linear combinations are labels of the corresponding incoming edges from the children) and gates labelled ˆcompute the products of their inputs in a fixed order. The formula is said to be homogeneous if each gate computes a homogeneous polynomial (of some degree). More precisely, each gate in the formula is associated with an integer d g such that • If g is a leaf, then d g " 0 or 1 depending on whether the leaf is labelled by a constant from F or a variable from X.

• If g is a `gate with children g 1 , . . . , g r , then d g " d g 1 " ¨¨¨" d gr .

• If g is a ˆgate with children g 1 , . . . , g r , then d g " d g 1 `¨¨¨`d gr .

Moreover, the formula is ordered set-multilinear w.r.t. the ordered partition pX 1 , . . . , X d q if for each gate g of the formula, there is an interval I g " ti, i `1, . . . , i `t ´1u Ď rds such that the polynomial computed by g lies in the space F sm xpX i , . . . , X i`t´1 qy. More precisely, we have for each gate g an interval I g Ď rds such that the following hold.

• If g is a leaf, then I g " H if g is labelled by a constant from F and I g " tiu if g is labelled by a variable from X i .

• If g is a `gate with children g 1 , . . . , g r , then I g " I g 1 " ¨¨¨" I gr .

• If g is a ˆgate with children g 1 , . . . , g r (multiplied in this order), then I g is a disjoint union of I g 1 , . . . , I gr with max I g 1 ă max I g 2 ă ¨¨¨ă max I gr .

It is easy to see that if F is an ordered set-multilinear formula, then each gate g computes a homogeneous polynomial of degree |I g | and hence any non-commutative ordered set-multilinear formula is in particular homogeneous. The following lemma says that the two models are essentially equivalent.

Lemma 6. Assume P P F sm xpX 1 , . . . , X d qy has a non-commutative homogeneous formula F of size s and product-depth at most ∆ (for some ∆ ě 1). Then P also has a non-commutative ordered set-multilinear formula of size at most s and product-depth at most ∆.

Proof. Let F be a non-commutative homogeneous formula for P . We recall that for such a formula, each node g is associated with a degree d g . We start by labelling the nodes g of F by intervals I g Ď rds such that |I g | " d g . We do it inductively (starting by the root):

• the output node is labelled by rds,

• if g is a `gate with children g 1 , . . . , g r , then we choose I g 1 " I g 2 " . . . " I gr " I g ,

• if g is a ˆgate with children g 1 , . . . , g r (in this order), then we have I g " ra, a `dg ´1s for some a. We choose for 1 ď j ď r, I g j " ra `řj 1 ăj d g j 1 , a `řj 1 ďj d g j 1 ´1s (notice they actually form an ordered partition of I g ).

From this labelled form of F , we define our new formula F 1 by modifying some of its degree-1 leaves. More precisely, if a degree-1 leaf g of F computing a variable from X i is labelled by the interval tiu, we let it unchanged. If it is labelled by another interval, we change this leaf to 0.

To any gate g of F , we associate its corresponding gate g 1 in F 1 . We can see now by induction on the formula that the polynomial computed by g 1 equals the projection of the polynomial computed by g on F sm xX Ig y. Indeed,

• if g is a leaf of F which computes a variable x from X i , then its projection on F sm xX Ig y is x if I g " tiu and 0 otherwise,

• if g is a `gate with children g 1 , . . . , g r , then the projection of g is the sum of the projections of the g j ,

• if g is a ˆgate with children g 1 , . . . , g r , then the projection of g along the interval I g equals the ordered product of the projections of g j along the intervals I g j .

Given the above lemma, we use the terminology 'non-commutative homogeneous formula' or 'non-commutative set-multilinear formula' or 'non-commutative ordered set-multilinear formula' interchangeably.

A non-commutative layered Algebraic Branching Program [START_REF] Nisan | Lower bounds for non-commutative computation[END_REF] (ABP) A is a directed acyclic graph with layers labelled 0, . . . , d, where the first and last layer have a single source vertex s and sink vertex t each, all edges go from a layer labelled i to a layer labelled i`1 (for 0 ď i ă d), and each such edge is labelled with a variable 10 in X i`1 . The polynomial P A P F sm xpX 1 , . . . , X d qy computed by the ABP is the sum, over all the paths ρ going from s to t, of the product of the edge labels of the edges of ρ (in increasing order of the source layer). A commutative setmultilinear ABP is defined in the same way, except that the polynomial P A is interpreted as an element of F sm rpX 1 , . . . , X d qs. 11 The width of the ABP A is the maximum number of vertices in any layer.

The following fact is standard and easy to show. An analogous fact also holds for commutative set-multilinear ABPs.

Fact

ABPs with large relative rank

We note that for every w which does not have too much bias, there is a polynomial P w P F sm xXpwqy that has large rank w.r.t. w and is a simple projection of a small instance of the Iterated Matrix Multiplication polynomial.

The following was proved in the commutative set-multilinear setting in our earlier work [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF]. Essentially the same proof translates to the non-commutative setting. Theorem 8. Let w P A d be any word that is b-unbiased. Then, there is an explicit polynomial P w P F sm xXpwqy such that relrk w pP w q ě 2 ´|w rds |{2 and has a non-commutative layered ABP of width at most 2 b . Since a non-commutative set-multilinear ABP computing some polynomial f can be seen as a commutative set-multilinear ABP computing πpf q, Theorem 8 is still true in the commutative setting. (This was already proved in [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF].) Corollary 9. Let w P A d be any word which is b-unbiased. If there is a set-multilinear (resp. non-commutative set-multilinear) formula computing IMM n,d of size s where n ě 2 b , then there is also a set-multilinear (resp. non-commutative set-multilinear) formula of size at most s computing a polynomial P w P F sm xXpwqy such that relrk w pP w q ě 2 ´|w rds |{2 . Proof. By Theorem 8, we know that there is a non-commutative layered ABP of width at most 2 b computing a polynomial P w P F sm xXpwqy such that relrk w pP w q ě 2 ´b{2 . By Fact 7, the polynomial P w can be obtained from IMM n,d via a simple variable substitution. If IMM 2 b ,d has 10 One can also define the labels to be homogeneous linear polynomial in Xi`1, but this more restrictive definition is sufficient in our setting. 11 There is another, more general, definition of a set-multilinear ABP due to Arvind and Raja [START_REF] Arvind | Some lower bound results for set-multilinear arithmetic computations[END_REF]. This definition is not suitable for our purposes here.

a formula F of size s, applying this substitution to F yields a formula F 1 (also of size at most s) computing P w . It is easy to check that F 1 is a non-commutative set-multilinear formula.

For the commutative setting, we apply the set-multilinear analog of the above argument w.r.t. the polynomial πpP w q.

Product lemma

We recall a well-known property of formulas. Analogs of this property have been proved in various previous settings (see, e.g. [START_REF] Shpilka | Arithmetic circuits: A survey of recent results and open questions[END_REF]Chapter 3]) but as far as we know, the statement below does not appear anywhere. We give the (fairly standard) proof.

Lemma 10 (Product lemma). Assume that F is a set-multilinear formula with at most s leaves. Then, we can write

F " s ÿ i"1 ź j"1 F i,j
where " log 2 d and for each i P rss, the product is set-multilinear. Moreover, if F has productdepth at most ∆ with ∆ ď ln d, then we can choose " ∆d 1{∆ ´∆.

Proof. We prove the result by induction on the number of leaves. If the formula has no leaves (i.e., computes 0), then the result is trivial.

So assuming that the lemma is proved for formulas of at most s leaves, let us prove it for a formula F with s `1 leaves.

A leaf α will be called maximal if for each multiplication gate β on the path from the root ρ to α, the child of β along this path has maximal degree amongst the children of β.

Let α be a maximal leaf of F . Let β 1 , . . . , β p (p ď ∆) be the multiplication gates which lie on the path between the root and α. For each β i , let us denote by β i,1 its child on the path from the root to α and by β i,2 , . . . , β i,r i its other children. If µ is a gate of F , we will denote by Fµ the polynomial computed by the subformula rooted in µ. Then, we can easily proved by induction on p that:

Claim 11. F " Fα p ź i"1 ˜ri ź j"2 Fβ i,r j ¸`F αÐ0
where F αÐ0 is the subformula we get by replacing the gate α by 0. Furthermore the product is still set-multilinear.

Proof. If p " 0, then F " Fα `F αÐ0 . Let us show the result for p `1. Let F " F 1 `. . . `Ft where α is in F 1 . So in the subtree rooted in β 1,1 , there are p multiplication gates between the root and α. By induction hypothesis, we have

F " ˜F α p`1 ź i"2 ˜ri ź j"2 Fβ i,r j ¸`F β 1,1 αÐ0 ¸¨r 1 ź j"2 Fβ 1,j `F 2 `. . . `F s .
The result follows from

F αÐ0 " F β 1,1 αÐ0 ¨rp`1 ź j"2 F β 1,j `F2 `. . . `Fs .
Let us come back to the proof of Lemma 10. The formula F αÐ0 has at most s leaves. So by induction hypothesis,

F αÐ0 " s ÿ i"1 ź j"1 F i,j .
So it is sufficient to prove that 1 `řp i"1 pr i ´1q ě . The maximality condition and the homogeneity of the formula ensure that for all i, degpβ i q ď r i degpβ i,1 q " r i degpβ i`1 q. In particular, ś p i"1 r i ě d. By the AM-GM inequality, we can bound the number of factors by

1 `p ÿ i"1 pr i ´1q ě 1 ´p `p ˜p ź i"1 r i ¸1{p ě 1 ´p `pd 1{p .
Finally, the derivative of x Þ Ñ xd 1{x is negative for 0 ă x ă ln d, and positive for x ą ln d.

Hence, the number of factors is always bounded by below by 1 `pe ´1q ln d ą log 2 d since pe ´1q ln 2 ą 1. Moreover, when ∆ ď ln d, we have a better lower bound ∆d 1{∆ ´∆.

Lower bounds for large depth formulas

Here we prove Theorem 1. We start with a definition and the main observation, which follows simply from the properties of relrk from an earlier section.

Definition 12 (Bias of a word w.r.t. a partition). Let S " pS 1 , . . . , S q be an ordered partition of rds (each S i Ď rds). We assume that the S i s are ordered with respect to their maximal elements (i.e., i ă j ùñ maxpS i q ă maxpS j q). Let w P Z d be arbitrary. Given a partition S " pS 1 , S 2 , . . . , S q of rds, we define the S-bias of w -biaspS, wq -to be the quantity

ř jPr s |w S j | where |w S j | " | ř iPS j w i |.
Note that unlike biaspwq which we introduced earlier, the values of biaspS, wq do not correspond to sums of w i s over some intervals, but over the parts of S. Lemma 13. Let w P Z d be arbitrary. Assume S " pS 1 , . . . , S q is an ordered partition of rds such that biaspS, wq ě r. Then, for any choice of polynomials f j P F sm rXpw S j qs (j P r s), we have relrk w pf 1 ¨f2 ¨¨¨f q ď 2 ´r{2 .

Proof. We know that relrk w pf 1 ¨¨¨f r q " ź j"1 relrk w| S j pf j q ď ź j"1

2 ´|w S j |{2 ď 2 ´r{2
where the equality follows from the multiplicativity of relrk and the inequality follows from the imbalance bound (Claim 5).

To find w that has high bias w.r.t. a given ordered interval partition, we use a random restriction idea. Lemma 14 (Random restrictions induce high bias). Let k be any positive integer. There is a probability distribution D on k-unbiased w P Z d such that for any partition S " pS 1 , . . . , S q of rds and any ε ě 1{k, we have Pr w"D rbiaspS, wq ď εk s ď p6εq {2 .

Proof. We first define the probability distribution D. Choose a function u : t0, . . . , du Ñ t´k, ´k `1, . . . , k ´1, ku by setting up0q " 0 and choosing upiq independently and uniformly at random from t´k, . . . , ku. Now, we fix w P Z d so that w i " upiq ´upi ´1q for each i P rds. Note that for any interval, we have w rts " u t ´u0 " u t (with t ď d) and hence in particular w is k-unbiased.

Note the following property of w, which will be important in the sequel. Given any i P rds and conditioned on up0q, . . . , upi ´1q, the random variable w i is uniformly distributed in some interval of length 2k `1.

For each j P r s, let E j denote the event that |w S j | ď εk. Note that we have So to prove the lemma it suffices to prove that for any B Ď r s of size at least {2, we have

Pr w r ľ jPB E j s ď p3ε{2q {2 . (1)
We show that (1) follows easily using a conditioning argument. Fix some B Ď r s such that B " tj 1 ă ¨¨¨ă j t u. We have

Pr w r ľ jPB E j s " Pr w rE j 1 ^¨¨¨^E jt s " t ź p"1 Pr w rE jp | E j 1 ^¨¨¨^E j p´1 s. (2)
Note that for any p P rts, the event E j 1 ^¨¨¨^E j p´1 depends only on up0q, . . . , upq 1 q where q 1 " max S 1 Y ¨¨¨Y S p´1 . Let q " max S p and note that the order chosen of the parts of S implies q ą q 1 . So let us condition on any choice of up0q, . . . , upq ´1q such that E j 1 ^¨¨¨^E j p´1 holds. Now, conditioned on up0q, . . . , upq ´1q we have w S jp " w q `θ where θ P R is fixed.

As noted above, conditioned on up0q, . . . , upq ´1q, wpqq is still uniformly distributed over an interval of length 2k `1. In particular, the probability that |w S jp | " |w q `θ| ď εk is at most

2εk `1 2k `1 ď 3εk 2k `1 ď 3ε{2
where for the first inequality we used the fact that ε ě 1{k. As the above holds for any conditioning of up0q, . for any B Ď r s of size t. This implies (1) and thus finishes the proof of the lemma.

We are now ready to prove the main theorem.

Proof of Theorem 1. If log d ď 2 log n log log n , then the result is trivial, so we will assume this is not the case. We assume without loss of generality that n is a power of 2 and that k " log 2 n. Assume IMM n,d has a set-multilinear formula F of size at most s. We assume that the input variables of IMM n,d are partitioned into pX 1 , . . . , X d q where X i is the set of variables in the ith matrix.

Using the Product Lemma (Lemma 10), we have

IMM n,d " s ÿ i"1 ź j"1 F i,j (3)
where ě log d and for each i P rss, there is a partition S i " pS i,1 , . . . , S i, q such that F i,j is a set-multilinear polynomial in the variables pX p : p P S i,j q. If F has product-depth ∆ ď ln d, then we may further assume that " ∆d 1{∆ ´∆.

We will show that for any ε ě 1{k, we have

s ě mintp1{εq Ωp q , 2 Ωpεk q u. (4)
Given the above bound, we can set ε " plog k{kq " Θplog log n{ log nq to finish the proof. It therefore suffices to prove (4). By Lemma 14, there is a probability distribution over k-unbiased words w P Z d such that for any ε ě 1{k we have Pr w rDi P rss : biaspS i , wq ď εk s ď p6εq {2 ¨s where the inequality uses a union bound.

If s ě p1{6εq {2 , then the inequality (4) holds trivially and we are done. So we assume s ă p1{6εq {2 . In particular, we see that there is a w such that biaspS i , wq ą εk for each i P rss and fix such a w for the rest of the proof.

Since w is k-unbiased, we know by Corollary 9 that there is a polynomial P w which is a setmultilinear restriction of IMM 2 k ,d " IMM n,d such that relrk w pP w q ě 2 ´k{2 . Thus, by applying this linear substitution to both sides of (3) we get

P w " s ÿ i"1 ź j"1 P i,j
where P i,j is the result of applying the linear substitutions to all the variables of F i,j . Note in particular that P i,j is a set-multilinear polynomial in just the variables of Xpw S i,j q. Hence, by Lemma 13, we have for each i P rss,

relrk w ˜ ź j"1 P i,j ¸ď 2 ´εk {2 .
On the other hand, by the sub-additivity of relrk we have

2 ´k{2 ď relrk w pP w q ď s ÿ i"1 relrk w ˜ ź j"1 P i,j ¸ď s ¨2´εk {2 .
Using the fact that log log n ě 2 log n and ε " plog kq{k, this implies that s ě 2 Ωpεk q implying (3) and finishing the proof.

Non-commutative homogeneous lower bound

In this section, we prove Theorem 4, which yields a stronger lower bound for non-commutative homogeneous formulas of small depth. In view of Lemma 6, it suffices to prove the lower bound for non-commutative ordered set-multilinear formulas.

Proposition 15. Let d, k ě 1 and any positive integer ∆ ď plog 2 dq{3. There is a w ∆ P Z d that is balanced and k2 ∆ -unbiased such that for any non-commutative ordered set-multilinear formula F of product-depth ∆ over Xpw ∆ q of size at most s, we have relrk w pF q ď s ¨expp´kd 1{∆ {10q.

Corollary 16. Let n, d, ∆ P Nzt0u. Any non-commutative ordered set-multilinear formula F of product-depth ∆ computing IMM n,d has size at least n Ωpd 1{∆ {2 ∆ q .

Proof. We assume that ∆ ď log d{3 since otherwise the result is trivial.

We now split the analysis into two cases. If 2 ∆ ě log n, then we need to argue a lower bound of exppΩpd 1{∆ qq. For this, we appeal to a result of Nisan and Wigderson [START_REF] Nisan | Lower bounds on arithmetic circuits via partial derivatives[END_REF] which yields such a lower bound for commutative set-multilinear formulas of product-depth ∆. This also implies a lower bound for the non-commutative case, as we can just treat any non-commutative set-multilinear formula for IMM n,d as a commutative formula for the same polynomial. Hence, we are done. Now assume that 2 ∆ ă log n. Fix integer k " tlogpn 1{2 ∆ qu ě 1 such that there is a balanced word w as guaranteed by Proposition 15 that is tlog nu-unbiased. By Corollary 9, if IMM n,d has a set-multilinear formula F of size s and product-depth ∆, then so does some polynomial P w such that relrk w pP w q " 1. By Proposition 15, we must then have s ě exppΩpkd 1{∆ qq " n Ωpd 1{∆ {2 ∆ q . This finishes the proof.

Our previous result [START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF] proves a weaker bound than the one above for commutative setmultilinear formulas under the additional assumption that d " Oplog nq. This result is incomparable to that one, as the model is weaker but the quantitative bounds obtained are stronger.

Proof of Proposition 15. Let us begin by defining w ∆ . For simplicity, let us assume that d " r ∆ ´1 for some odd number r ě 3. (This assumption can easily be removed by fixing r to be the largest odd number such that r ∆ ´1 ď d and working with a word w that is as defined below on the first d 1 " r ∆ ´1 co-ordinates and 0 on all other co-ordinates. In particular we can always get r ě pd `1q 1{∆ ´2 ě d 1{∆ {2 ě 3 where the last two inequalities uses ∆ ď plog dq{3.) More generally, let d i " r i ´1 for i ď ∆.

Define, for each i ď ∆, a word w i P Z d i as follows.

w 1 " pk, ´k, k, ´k, ¨¨¨, k, ´kq w i`1 " pw i , pB i `kq, w i , ´pB i `kq, ¨¨¨, ´pB i `kq, w i q (5)

where B i :" max I |w i I | where I ranges over intervals contained in rd i s that begin at 1 or end at d i (i.e. the intervals that measure how unbiased w i is). Note that w i`1 contains exactly r copies of w i .

It can be checked by induction on i that the following hold.

(P1) Each w i is balanced: the sum of its entries is 0.

(P2) For every interval I Ď rd i s that begins at 1, |w i I | ě 0 and for every interval I Ď rd i s that ends at d i ,

|w i I | ď 0. (P3) If i ă ∆, then B i`1 ď 2B i `k.
The last condition implies that B i ď kp2 i ´1q ď k2 i for each i P r∆s. In particular, the word w ∆ is balanced and k2 ∆ -unbiased as claimed.

We call the positions of w i`1 that contain pB i `kq or ´pB i `kq the extremal positions of w i`1 . We have set things up so that w i`1 has exactly r ´1 many extremal positions.

We prove the following stronger claim by induction on the product-depth. For i ď ∆, let F be any (non-commutative ordered set-multilinear) formula of product-depth i over a XpW q where W is a (contiguous) subword of w ∆ that contains w i . Then relrk W pF q ď s ¨expp´kr{5q where s denotes the size of F . This claim finishes the proof since r ě d 1{∆ {2.

The base case of the induction corresponds to product-depth 1. Let F be a formula over XpW q where W contains w 1 as a subword. We have F " F 1 `¨¨¨`F s where F i s are products of linear functions. Note that by Claim 5, any linear function L j over the variable set XpW j q satisfies relrk W j pL j q ď 2 ´|W j |{2 . In particular, each product of linear functions F i satisfies relrk W pF i q ď 2 ´řj |W j |{2 . Hence, by the subadditivity of relrk W p¨q, we have relrk W pF q ď s ÿ i"1 relrk W pF i q ď s ¨2´ř j |W j |{2 ď s ¨2´ř j |w 1 j |{2 ď s ¨expp´kr{5q.

where for the second-last inequality we used the fact that w 1 is a subword of W and for the last one, the fact that r ě 3. Now for the inductive case. Assume the above is already proved for depth i ă ∆ and consider depth i `1. Again assume that W contains w i`1 and F has product-depth i `1. We have F " F 1 `¨¨¨`F s where each F i has a product gate as output gate. By subadditivity of relrk W it suffices to show that for each i P rss, we have relrk W pF i q ď s i ¨expp´kr{5q, [START_REF] Gupta | Approaching the chasm at depth four[END_REF] where s i is the size of the subformula F i . Fix any F i . We have F i " G 1 ¨¨¨G which corresponds to splitting the word W into disjoint subwords W 1 , . . . , W . Let s i,j denote the size of G j . We consider two cases.

1. There is a j P r s such that W j contains a copy of w i : In this case, we can bound relrk W pF i q by relrk W pF i q ď relrk W j pG j q ď s i,j ¨expp´kr{5q ď s i ¨expp´kr{5q.

2.

There is no such j P r s: In this case, the extremal positions of w i`1 are in different words (if two extremal positions belonged to the same word W j , then W j would contain a copy of w i , which is assumed to be false). Let W j 1 , . . . , W j r´1 be the words that contain the extremal positions.

By the construction of w i`1 in (5), each such word W jp (p P rr ´1s) is a (possibly empty) partial suffix u of a copy of w i , followed by the extremal position, which is then followed by a (possibly empty) partial prefix v of w i . By our choice of B i , it follows that the sum of entries of W jp is at least k in absolute value for each p P rr ´1s. To see this, note that if the entry in the extremal position is positive, then by (P2) above, the sum of the entries of v only increase this value, while the sum of the entries of u can only reduce this value by B i , hence implying that the overall sum is at least k. A similar argument shows that if the extremal position has a negative entry, the sum of the entries of W jp is at most ´k and hence at least k in absolute value. Hence, by Claim 5, we have relrk W jp pG jp q ď 2 ´k{2 for each p P rr ´1s. We can thus bound relrk W pF i q by relrk W pF i q ď 2 ´kpr´1q{2 ď expp´kr{5q ď s i expp´kr{5q.

We have thus proved [START_REF] Gupta | Approaching the chasm at depth four[END_REF] which completes the induction.

Finally, we can even get a depth hierarchy result. We notice that there are polynomials P ∆ w set-multilinear over Xpw ∆ q which are computable by non-commutative ordered set-multilinear polynomial-sized formulas of product-depth ∆ `1 where the words w are those chosen in the proof of Proposition 15. Intuitively, these polynomials are constructed from nested inner products according to w. Indeed, let us define

P 1
w `Xra,a`r´2s ˘" pr´1q{2 ź u"1

2 k ÿ v"1
x a`2u´2,v x a`2u´1,v , and P i`1 w `Xra,a`r i`1 ´2s " P i w `Xra,a`r i ´2s ˘¨pr´1q{2 ź u"1

2 B i `k ÿ v"1 2 ź j"1
x a`p2u`j´2qr i ´1,v P i w `Xra`p2u`j´2qr i ,a`p2u`j´1qr i ´2s where X ra,bs corresponds to the sets of variables Ť iPra,bs X i . Notice that P i w is always associated with an interval of variables of length r i ´1. Finally, each set X i has at most max i p2 k`B i q ď 2 k2 i variables, so the polynomials P i w depend on at most N " d2 k2 ∆ variables. It is clear by definition that P i w is computed by a non-commutative ordered set-multilinear circuit of product-depth ∆ `1 and size at most 2∆ ¨r ¨max i p2 B i `kq ď 2∆d2 k2 ∆ ď Op∆ ¨N q. Moreover, the inner product structure ensures that relrkpP i w q " 1 for all i. Consequently, combined with Proposition 15, we get Corollary 17. Let ∆ be a positive constant and N, d be growing parameters. There exist non-commutative homogeneous N -variate polynomials of degree d which are computed by noncommutative ordered set-multilinear formulas of product-depth ∆ `1 and size OpN q, but such that any such formula of product-depth ∆ has size at least s ě N Ωpd 1{∆ q .

Corollary 3 .

 3 Any non-commutative homogeneous formula computing IMM n,n must have size at least n Ωplog log nq .

  . . , upq ´1q, it implies that

	Pr w rE jp | E j 1 ^¨¨¨^E j p´1 s ď 3ε{2
	for any p P rts. By (2), we have
	Pr w r jPB ľ	E j s ď p3ε{2q t

More precisely, any internal node v with children u1, . . . , ur is labelled either ˆor `. In the former case, the nodes represent the products of its inputs. In the latter case, it computes a linear combination of the inputs, where the coefficients of the linear combinations are field elements labelling the edges between the uis and v.

This result holds for super-constant but small depths as well.

One can also get lower bounds for larger degrees by reducing from the case of d " Oplog nq. However, we do not get an improved lower bound as the degree increases.

Equivalently, the multiplications take place in the non-commutative polynomial ring Fxx1, . . . , xN y.

As mentioned above, the best lower bound we know in this setting against set-multilinear formulas is n d expp´Op∆qq due to[START_REF] Limaye | Superpolynomial lower bounds against low-depth algebraic circuits[END_REF]. Even for product-depth 3, this does not get the right bound of n Ωpd 1{3 q .

Lagarde, Limaye and Srinivasan[START_REF] Lagarde | Lower bounds and pit for noncommutative arithmetic circuits with restricted parse trees[END_REF] proved a non-FPT bound for a special kind of non-commutative formulas that are called Unique Parse Tree (UPT) formulas, which essentially reproves Nisan and Wigderson's lower bound for pure circuits.

Our quantitative bound is weaker, but the model is stronger.

For the sake of simplicity of exposition, we consider the matrix rank measure here. In the proof we use a slightly different measure called the relative rank. We define that formally in Section 2.

We are abusing the notion a bit and using Fi to also denote the polynomial computed by the formula Fi.

* Funded by SERB project File no. MTR/2017/000909. † Funded by the project BIRCA from the IDEX of Univ. Grenoble Alpes (Contract 183459). The author also benefited from an accommodation paid by IIT Bombay during a visit of the other two authors.