Lower bounds by Birkhoff interpolation

DOI10.1016/J.JCO.2016.10.001zbMATH Open1357.41002OpenAlexW820240838MaRDI QIDQ511113FDOQ511113

Authors Ignacio García Marco, Pascal Koiran

Publication date 14 February 2017

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.02015

zbMATH Keywords

lower boundspolynomial interpolationWaring problemarithmetic circuitreal polynomial

Mathematics Subject Classification ID

Numerical interpolation (65D05) Interpolation in approximation theory (41A05)

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 $Omega$($sqrt$ 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").

Recommendations

• Lower bounds for sums of powers of low degree univariates
• Lower bounds for polynomial evaluation and interpolation problems
• On the solvability of the Birkhoff interpolation problem
• Birkhoff Polynomial Basis
• The proper interpolation space for multivariate Birkhoff interpolation

Cites work

• scientific article; zbMATH DE number 773851 (Why is no real title available?)
• A Partial Characterization of Poised Hermite–Birkhoff Interpolation Problems
• A super-polynomial lower bound for regular arithmetic formulas
• Approaching the chasm at depth four
• Arithmetic circuits: a chasm at depth 3
• Arithmetic circuits: the chasm at depth four gets wider
• Condition. The geometry of numerical algorithms
• Improved Bounds for Reduction to Depth 4 and Depth 3
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• Lower bounds for sums of powers of low degree univariates
• On the Alexander-Hirschowitz theorem
• On the ranks and border ranks of symmetric tensors
• The limits of depth reduction for arithmetic formulas
• The method of shifted partial derivatives cannot separate the permanent from the determinant
• The solution to the Waring problem for monomials and the sum of coprime monomials

Cited in

(6)

• Optimal Birkhoff interpolation and Birkhoff numbers in some function spaces
• Lower complexity bounds for interpolation algorithms
• Lower bounds for sums of powers of low degree univariates
• Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)
• Optimal Hermite-Fejér interpolation of algebraic polynomials and the best one-sided approximation on the interval \([-1,1]\)
• On the linear independence of shifted powers

This page was built for publication: Lower bounds by Birkhoff interpolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511113)