An Algebraic Formula for a polynomial $P\in F[x_1,\ldots,x_N]$ is an algebraic expression for $P(x_1,\ldots,x_N)$ using variables, field constants, additions and multiplications. Such formulas capture an algebraic analog of the Boolean complexity class $\mathrm{NC}^1.$ Proving lower bounds against this model is thus an important problem.

It is known that, to prove superpolynomial lower bounds against algebraic formulas, it suffices to prove good enough lower bounds against restricted kinds of formulas known as Set-Multilinear formulas, for computing a polynomial $P(x_1,...,x_N)$ of degree $O(\log N/\log \log N)$. In the past, many superpolynomial lower bounds were found, but they are of the form $\Omega(f(d) poly(N))$ (where $f$ is typically a subexponential function) which is insufficient to get lower bounds for general formulas. Recently, the authors proved the first non-FPT lower bounds, i.e., a lower bound of the form $N^{\Omega{(f(d)})}$, 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 $(\log n)^{\Omega(\log d)}$ 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/\Delta}/2^{O(\Delta)}}$, which yields non-FPT bounds for depths up to $o(\sqrt{\log d}).$ In comparison, the previous bound works in the harder commutative set-multilinear setting, but only up to depths $o(\log \log d)$.
Moreover, our lower bound holds for all values of $d$, as opposed to the previous set-multilinear lower bound, which holds as long as $d$ is small, i.e., $d = O(\log n)$.