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

Author

S. Chillara, N. Limaye and S. Srinivasan

Published

September 15, 2017

Link to the article

Authors

Suryajith Chillara, Nutan Limaye and Srikanth Srinivasan

Publisher Information

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 well-known divide-and-conquer 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 product-depth \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 product-depth \Delta for the same polynomial of the above form must have a size of \exp(\Omega(d^{1/\Delta})). In particular, any polynomial-sized multilinear formula for IMM_d must have depth \Omega(\log d), and any polynomial-sized 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.

  • 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.

  • Circuits vs. formulas: Any circuit of size s and product-depth \Delta can be converted into a formula of product-depth \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 product-depth \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 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 \Delta = o(\log s), general formulas of size s and product-depth \Delta cannot be converted to multilinear formulas of size s^{O(1)} and product-depth \Delta, when the underlying field has characteristic zero.