Name
Abstract | ||
|---|---|---|
We show that any depth-4 homogeneous arithmetic formula computing the Iterated Matrix Multiplication polynomial IMMn,d -- the (1, 1)-th entry of the product of d generic n × n matrices -- has size nΩ(log n), if d = Ω (log2 n). More-over, any depth-4 homogeneous formula computing the determinant polynomial Detn -- the determinant of a generic n × n matrix -- has size nΩ(log n). |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2591796.2591823 | STOC |
Keywords | Field | DocType |
computations on polynomials,shifted partial derivatives,lower bounds,arithmetic circuits,theory,unbounded-action devices | Discrete mathematics,Binary logarithm,Arithmetic circuits,Combinatorics,Polynomial,Matrix (mathematics),Homogeneous,Arithmetic,Matrix multiplication,Iterated function,Mathematics | Conference |
Citations | PageRank | References |
9 | 0.54 | 23 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeraj Kayal | 1 | 263 | 19.39 |
| Nutan Limaye | 2 | 134 | 20.59 |
| Chandan Saha | 3 | 227 | 16.91 |
| Srikanth Srinivasan | 4 | 132 | 21.31 |