Name
Abstract | ||
|---|---|---|
We prove an exponential lower bound for expressing a polynomial as a sum of product of low arity polynomials. Specifically, we show that for the iterated matrix multiplication polynomial, IMMd,n (corresponding to the product of d matrices of size n × n each), any expression of the form IMMd,n = s ∑ |
Year | Venue | Field |
|---|---|---|
2015 | Electronic Colloquium on Computational Complexity (ECCC) | Discrete mathematics,Combinatorics,Arity,Exponential function,Polynomial,Of the form,Upper and lower bounds,Matrix (mathematics),Iterated function,Matrix multiplication,Mathematics |
DocType | Volume | Citations |
Journal | 22 | 1 |
PageRank | References | Authors |
0.36 | 17 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeraj Kayal | 1 | 263 | 19.39 |
| Chandan Saha | 2 | 227 | 16.91 |