Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication

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.

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 px 1 , ..., x N q of degree Oplog N log log N q. In the past, many superpolynomial lower bounds were found, but they are of the form Ωpf pdq polypN qq (where f is typically a subexponential function) which is insufficient to get lower bounds for general formulas. Recently, the authors proved [13] 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.