HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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 metadata

Cited literature [17 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01172296
Contributor : Pascal Koiran Connect in order to contact the contributor
Submitted on : Tuesday, July 7, 2015 - 11:27:52 AM
Last modification on : Saturday, September 11, 2021 - 3:18:22 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

41

Files downloads

372