Lower bounds by Birkhoff interpolation

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

Ignacio García Marco, Pascal Koiran

Publication date: 14 February 2017

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

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").

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)

Cites Work

• Condition
• The solution to the Waring problem for monomials and the sum of coprime monomials
• Title not available (Why is that?)
• Arithmetic circuits: the chasm at depth four gets wider
• On the ranks and border ranks of symmetric tensors
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• Arithmetic circuits: a chasm at depth 3
• Improved Bounds for Reduction to Depth 4 and Depth 3
• A super-polynomial lower bound for regular arithmetic formulas
• Approaching the Chasm at Depth Four
• On the Alexander-Hirschowitz theorem
• A Partial Characterization of Poised Hermite–Birkhoff Interpolation Problems
• Lower Bounds for Sums of Powers of Low Degree Univariates
• The method of shifted partial derivatives cannot separate the permanent from the determinant
• The limits of depth reduction for arithmetic formulas

Cited In (6)

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

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)