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

In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted ${\mathrm{I}\mathrm{M}\mathrm{M}}_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 $\mathrm{\Delta }\le \log d$, we show that any product-depth $\mathrm{\Delta }$ multilinear formula for ${\mathrm{I}\mathrm{M}\mathrm{M}}_d$ must have size $\exp (\mathrm{\Omega }(\mathrm{\Delta }{d}^{1\mathrm{/}\mathrm{\Delta }}))\mathrm{.}$ It also follows from this that any multilinear circuit of product-depth $\mathrm{\Delta }$ for the same polynomial of the above form must have a size of $\exp (\mathrm{\Omega }(d^{1\mathrm{/}\mathrm{\Delta }}))\mathrm{.}$ In particular, any polynomial-sized multilinear formula for ${\mathrm{I}\mathrm{M}\mathrm{M}}_d$ must have depth $\mathrm{\Omega }(\log d)$, and any polynomial-sized multilinear circuit for ${\mathrm{I}\mathrm{M}\mathrm{M}}_d$ must have depth $\mathrm{\Omega }(\log d\mathrm{/}\log \log d)\mathrm{.}$ Both these bounds are tight up to constant factors.

1. Depth-reduction: A well-known result of Brent (JACM 1974) implies that any formula of size $s$ can be converted to one of size $s^{O(1)}$ and depth $O(\log s)$; further, this reduction continues to hold for multilinear formulas. Our lower bound implies that any depth-reduction in the multilinear setting cannot reduce the depth to $o(\log s)$ without a superpolynomial blow-up in size.
2. Separations from general formulas: Our result, along with a non-trivial upper bound for ${\mathrm{I}\mathrm{M}\mathrm{M}}_d$ implied by a result of Gupta, Kamath, Kayal and Saptharishi (SICOMP 2016), shows that for any size $s$ and product-depth $\mathrm{\Delta }=o(\log s),$ general formulas of size $s$ and product-depth $\mathrm{\Delta }$ cannot be converted to multilinear formulas of size $s^{\omega (1)}$ and product-depth $\mathrm{\Delta },$ when the underlying field has characteristic zero.