Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications

The complexity of Iterated Matrix Multiplication (IMM) is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within ${P}$. In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted ${IMM}_{d}$, and show that the well-known divide-and-conquer algorithm cannot be significantly improved at any depth as long as the formulas are multilinear. Formally, for each depth $\Delta \leq \log d$, we show that any product-depth $\Delta$ multilinear formula for ${IMM}_d$ must have size $\exp(\Omega(\Delta d^{1/\Delta})).$ It also follows from this that any multilinear circuit of product-depth $\Delta$ for the same polynomial of the above form must have a size of $\exp(\Omega(d^{1/\Delta})).$ In particular, any polynomial-sized multilinear formula for ${IMM}_d$ must have depth $\Omega(\log d)$, and any polynomial-sized multilinear circuit for ${IMM}_d$ must have depth $\Omega(\log...