Record Details

LOWER BOUNDS FOR DEPTH-4 FORMULAS COMPUTING ITERATED MATRIX MULTIPLICATION

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title LOWER BOUNDS FOR DEPTH-4 FORMULAS COMPUTING ITERATED MATRIX MULTIPLICATION
 
Creator FOURNIER, H
LIMAYE, N
MALOD, G
SRINIVASAN, S
 
Subject ARITHMETIC CIRCUITS
COMPLEXITY
CHASM
arithmetic circuits
depth four
iterated matrix product
shifted partial derivative measure
lower bound
 
Description 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 x n, IMMn,d, has size n(Omega(root 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 fanins of the. 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 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 IMMn,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.
 
Publisher SIAM PUBLICATIONS
 
Date 2016-01-15T09:49:40Z
2016-01-15T09:49:40Z
2015
 
Type Article
 
Identifier SIAM JOURNAL ON COMPUTING, 44(5)1173-1201
0097-5397
1095-7111
http://dx.doi.org/10.1137/140990280
http://dspace.library.iitb.ac.in/jspui/handle/100/18294
 
Language en