Lower complexity bounds for interpolation algorithms

DOI10.1016/j.jco.2010.10.003zbMath1277.65008MaRDI QIDQ2431336

Joos Heintz, Guillermo Matera, Pablo Solernó, Nardo Giménez

Publication date: 13 April 2011

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

Full work available at URL: http://hdl.handle.net/11336/113310

zbMATH Keywords

algorithm; valuation; lower complexity bound; Hermite-Lagrange interpolation; constructible map; geometrically robust map

Mathematics Subject Classification ID

65D05: Numerical interpolation

41A05: Interpolation in approximation theory

65Y20: Complexity and performance of numerical algorithms

Uses Software

• Eiffel

Cites Work

• The least solution for the polynomial interpolation problem
• The red book of varieties and schemes
• On the intrinsic complexity of elimination theory
• The hardness of polynomial equation solving
• Generic local structure of the morphisms in commutative algebra
• On multivariate polynomial interpolation
• On Multivariate Interpolation
• A continuity property of multivariate Lagrange interpolation
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Model Theory
• Constraint Databases
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item