Lower Bounds by Birkhoff Interpolation

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").
Document type :
Journal articles
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01172296
Contributor : Pascal Koiran <>
Submitted on : Tuesday, July 7, 2015 - 11:27:52 AM
Last modification on : Wednesday, November 20, 2019 - 8:09:09 AM
Long-term archiving on : Wednesday, April 26, 2017 - 12:45:13 AM

Files

birkhoff.arxiv.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : ensl-01172296, version 1
  • ARXIV : 1507.02015

Collections

Citation

Ignacio Garcia-Marco, Pascal Koiran. Lower Bounds by Birkhoff Interpolation. Journal of Complexity, Elsevier, 2017. ⟨ensl-01172296⟩

Share

Metrics

Record views

85

Files downloads

449