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 \times n$, $\mathrm{IMM}_{n,d}$, has size $n^{\Omega(\sqrt{d})}$ as long as $d = n^{O(1)}$. This improves the result of Nisan and Wigderson [Comput. Complexity, 6 (1997), pp. 217--234] for depth-4 set-multilinear formulas. We also study $\Sigma\Pi^{[O(d/t)]}\Sigma\Pi^{[t]}$ formulas, which are depth-4 formulas with the stated bounds on the fan-ins of the $\Pi$ gates. A recent depth reduction result of Tavenas [Lecture Notes in Comput. Sci. 8087, 2013, pp. 813--824] shows that any $n$-variate degree $d = n^{O(1)}$ polynomial computable by a circuit of size $\mathop{\mathrm{poly}}(n)$ can also be computed by a depth-4 $\Sigma\Pi^{[O(d/t)]}\Sigma\Pi^{[t]}$ formula of top fan-in $n^{O(d/t)}$. We show that any such formula computing $\mathrm{IMM}_{n,d}$ has top fan-in $n^{\Omega({d/t})}$, proving the optimality of Tavenas' result. This also strengthens a result of Kayal, Saha, and Saptharishi [Proceedings of STOC, 2014, pp. 146--153], which gives a similar lower bound for an explicit polynomial in VNP.