Smalldepth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
Authors
Suryajith Chillara, Nutan Limaye and Srikanth Srinivasan
Publisher Information
 Journal: SIAM Journal of Computing. 48(1): 7092, 2019
 Conference: STACS 2018, Pages 21:121:15
Abstract
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 $\mathrm{P}$. In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted $IMM_{d}$, and show that the wellknown divideandconquer algorithm cannot be significantly improved at any depth, as long as the formulas are multilinear.
Formally, for each depth $\Delta \leq \log d$, we show that any productdepth $\Delta$ multilinear formula for $IMM_d$ must have size $\exp(\Omega(\Delta d^{1/\Delta})).$ It also follows from this that any multilinear circuit of productdepth $\Delta$ for the same polynomial of the above form must have a size of $\exp(\Omega(d^{1/\Delta})).$ In particular, any polynomialsized multilinear formula for $IMM_d$ must have depth $\Omega(\log d)$, and any polynomialsized multilinear circuit for $IMM_d$ must have depth $\Omega(\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.

Depthreduction: A wellknown 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 depthreduction in the multilinear setting cannot reduce the depth to $o(\log s)$ without a superpolynomial blowup in size.

Circuits vs. formulas: Any circuit of size $s$ and productdepth $\Delta$ can be converted into a formula of productdepth $\Delta$ and size $s^{O(\Delta)}$. In the multilinear setting, we show that it is not possible to improve on this significantly for small depths. Formally, our results imply that for all large enough $s$ and $\Delta = o(\log s/\log \log s)$, there is an explicit multilinear polynomial $P_{s,\Delta}$ that has a syntactic multilinear circuit of size $s$ and is such that any multilinear formula of productdepth $\Delta$ computing $P_{s,\Delta}$ must have size $s^{\Omega(\Delta)}$.

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 nontrivial upper bound for $IMM_{d}$ implied by a result of Gupta, Kamath, Kayal and Saptharishi (SICOMP 2016), shows that for any size $s$ and productdepth $\Delta = o(\log s),$ general formulas of size $s$ and productdepth $\Delta$ cannot be converted to multilinear formulas of size $s^{O(1)}$ and productdepth $\Delta,$ when the underlying field has characteristic zero.