Chillara, Suryajith ;
Limaye, Nutan ;
Srinivasan, Srikanth
Smalldepth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
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 P. In this paper, we study the algebraic formula complexity of multiplying d many 2x2 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 <= 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.
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.
BibTeX  Entry
@InProceedings{chillara_et_al:LIPIcs:2018:8523,
author = {Suryajith Chillara and Nutan Limaye and Srikanth Srinivasan},
title = {{Smalldepth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {21:121:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770620},
ISSN = {18688969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8523},
URN = {urn:nbn:de:0030drops85235},
doi = {10.4230/LIPIcs.STACS.2018.21},
annote = {Keywords: Algebraic circuit complexity, Multilinear formulas, Lower Bounds}
}
27.02.2018
Keywords: 

Algebraic circuit complexity, Multilinear formulas, Lower Bounds 
Seminar: 

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Issue date: 

2018 
Date of publication: 

27.02.2018 