Small-depth 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): 70-92, 2019
- Conference: STACS 2018, Pages 21:1-21: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
Formally, for each depth
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
can be converted to one of size and depth ; 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 without a superpolynomial blow-up in size. -
Circuits vs. formulas: Any circuit of size
and product-depth can be converted into a formula of product-depth and size . 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 and , there is an explicit multilinear polynomial that has a syntactic multilinear circuit of size and is such that any multilinear formula of product-depth computing must have size . -
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
implied by a result of Gupta, Kamath, Kayal and Saptharishi (SICOMP 2016), shows that for any size and product-depth general formulas of size and product-depth cannot be converted to multilinear formulas of size and product-depth when the underlying field has characteristic zero.