Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1137/140990280 | SIAM JOURNAL ON COMPUTING |
Keywords | Field | DocType |
arithmetic circuits,depth four,iterated matrix product,shifted partial derivative measure,lower bound | Discrete mathematics,Combinatorics,Polynomial,Upper and lower bounds,Matrix (mathematics),Omega,Sigma,Multilinear map,Iterated function,Matrix multiplication,Mathematics | Journal |
Volume | Issue | ISSN |
44 | 5 | 0097-5397 |
Citations | PageRank | References |
16 | 0.64 | 17 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hervé Fournier | 1 | 185 | 18.10 |
| Nutan Limaye | 2 | 134 | 20.59 |
| Guillaume Malod | 3 | 54 | 4.53 |
| Srikanth Srinivasan | 4 | 132 | 21.31 |