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 × n, IMMn,d, has size nΩ(√d) as long as d = nO(1). This improves the result of Nisan and Wigderson (Computational Complexity, 1997) for depth 4 set-multilinear formulas. We also study ΣΠ[O(d/t)] ΣΠ[t] formulas, which are depth 4 formulas with the stated bounds on the fan-ins of the Π gates. A recent depth reduction result of Tavenas (MFCS, 2013) shows that any n-variate degree d = nO(1) polynomial computable by a circuit of size poly(n) can also be computed by a depth 4 ΣΠ[O(d/t)] ΣΠ[t] formula of top fan-in nO(d/t). We show that any such formula computing IMMn,d has top fan-in nΩ(d/t), proving the optimality of Tavenas' result. This also strengthens a result of Kayal, Saha, and Saptharishi (ECCC, 2013) which gives a similar lower bound for an explicit polynomial in VNP. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2591796.2591824 | STOC |
Keywords | DocType | Volume |
computations on polynomials,shifted partial derivatives,lower bounds,arithmetic circuits,theory,unbounded-action devices | Journal | 20 |
Citations | PageRank | References |
4 | 0.41 | 19 |
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 |