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

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted ${\mathrm{IMM}}_d$, and show that the well-known divide-and-conquer a…