Back to Search
Start Over
Lower bounds by Birkhoff interpolation.
- Source :
-
Journal of Complexity . Apr2017, Vol. 39, p38-50. 13p. - Publication Year :
- 2017
-
Abstract
- In this paper we give lower bounds for the representation of real univariate polynomials as sums of powers of degree 1 polynomials. We present two families of polynomials of degree d such that the number of powers that are required in such a representation must be at least of order d . This is clearly optimal up to a constant factor. Previous lower bounds for this problem were only of order Ω ( d ) , and were obtained from arguments based on Wronskian determinants and “shifted derivatives”. We obtain this improvement thanks to a new lower bound method based on Birkhoff interpolation (also known as “lacunary polynomial interpolation”). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0885064X
- Volume :
- 39
- Database :
- Academic Search Index
- Journal :
- Journal of Complexity
- Publication Type :
- Academic Journal
- Accession number :
- 121134493
- Full Text :
- https://doi.org/10.1016/j.jco.2016.10.001