Lower complexity bounds for interpolation algorithms

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

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

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

algorithmvaluationlower complexity boundHermite-Lagrange interpolationconstructible mapgeometrically robust map

Mathematics Subject Classification ID

Numerical interpolation (65D05) Interpolation in approximation theory (41A05) Complexity and performance of numerical algorithms (65Y20)

Related Items

Quiz games as a model for information hiding, On the bit complexity of polynomial system solving

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