Lower bounds by Birkhoff interpolation

DOI10.1016/j.jco.2016.10.001zbMath1357.41002arXiv1507.02015OpenAlexW820240838MaRDI QIDQ511113

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

real polynomiallower boundsWaring problempolynomial interpolationarithmetic circuit

Mathematics Subject Classification ID

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

Related Items (4)

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 ⋮ Reconstruction algorithms for sums of affine powers ⋮ Optimal Birkhoff interpolation and Birkhoff numbers in some function spaces

Cites Work

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

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