Name
Abstract | ||
|---|---|---|
We consider the problem of representing a univariate polynomial f(x) as a sum of powers of low degree polynomials. We prove a lower bound of Omega(root d/t) for writing an explicit univariate degree-d polynomial f(x) as a sum of powers of degree-t polynomials. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-47672-7_66 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Arithmetic circuits,Lower bounds,Sums of powers,Wronskian,Shifted derivatives | Discrete mathematics,Combinatorics,Power sum symmetric polynomial,Polynomial,Upper and lower bounds,Wronskian,Degree of a polynomial,Omega,Sums of powers,Univariate,Mathematics | Conference |
Volume | ISSN | Citations |
9134 | 0302-9743 | 5 |
PageRank | References | Authors |
0.53 | 14 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeraj Kayal | 1 | 263 | 19.39 |
| Pascal Koiran | 2 | 919 | 113.85 |
| Timothée Pecatte | 3 | 16 | 2.89 |
| Chandan Saha | 4 | 227 | 16.91 |