The complexity of Iterated Matrix Multiplication 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 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 log d , we show that any product-depth multilinear formula for IMM d must have size exp ( ( d 1 )) It also follows from this that any multilinear circuit of product-depth for the same polynomial of the above form must have a size of exp ( ( d 1 )) In particular, any polynomial-sized multilinear formula for IMM d must have depth ( log d ) , and any polynomial-sized multilinear circuit for IMM d must have depth ( log d log log d ) Both these bounds are tight up to constant factors.

Our lower bound has the following consequences for multilinear formula complexity.

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. On the other hand, 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: Shpilka and Yehudayoff (FnTTCS 2010) asked whether general formulas can be more efficient than multilinear formulas for computing multilinear polynomials. Our result, along with a non-trivial upper bound for IMM d implied by a result of Gupta, Kamath, Kayal and Saptharishi (SICOMP 2016), shows that for any size s and product-depth = o ( log s ) general formulas of size s and product-depth cannot be converted to multilinear formulas of size s (1) and product-depth when the underlying field has characteristic zero.