Lower bounds for depth 4 formulas computing iterated matrix multiplication

Abstract

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth 4 arithmetic formula computing the product of d generic matrices of size n × n, IMMn,d, has size nΩ(√d) as long as d = nO(1). This improves the result of Nisan and Wigderson (Computational Complexity, 1997) for depth 4 set-multilinear formulas.