Lower complexity bounds for interpolation algorithms

DOI10.1016/J.JCO.2010.10.003MaRDI QIDQ2431336zbMATH OpenOpenAlexFDO

Authors Nardo Giménez, Joos Heintz, Pablo Solernó, 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

algorithmlower complexity boundvaluationHermite-Lagrange interpolationconstructible mapgeometrically robust map

Mathematics Subject Classification ID

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

Recommendations

• A Lower Bound for Interpolation
• Lower bounds for polynomial evaluation and interpolation problems
• Computational Complexity of Sparse Rational Interpolation
• The complexity of evaluating interpolation polynomials
• scientific article; zbMATH DE number 421669
• scientific article; zbMATH DE number 917814
• Optimization-based computation of analytic interpolants of bounded complexity
• Lower bounds by Birkhoff interpolation
• An approximation algorithm for optimal piecewise linear interpolations of bounded variable products
• A class of interpolation algorithms for bounded real functions

Cites work

• scientific article; zbMATH DE number 3897078 (Why is no real title available?)
• scientific article; zbMATH DE number 3937310 (Why is no real title available?)
• scientific article; zbMATH DE number 3759547 (Why is no real title available?)
• scientific article; zbMATH DE number 108341 (Why is no real title available?)
• scientific article; zbMATH DE number 3592331 (Why is no real title available?)
• scientific article; zbMATH DE number 621807 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 953010 (Why is no real title available?)
• scientific article; zbMATH DE number 233957 (Why is no real title available?)
• scientific article; zbMATH DE number 3196340 (Why is no real title available?)
• A continuity property of multivariate Lagrange interpolation
• Constraint Databases
• Generic local structure of the morphisms in commutative algebra
• Kronecker's smart, little black boxes
• Model Theory
• On Multivariate Interpolation
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On multivariate polynomial interpolation
• On the intrinsic complexity of elimination theory
• The hardness of polynomial equation solving
• The least solution for the polynomial interpolation problem
• The red book of varieties and schemes

Cited in

(6)

• scientific article; zbMATH DE number 917814 (Why is no real title available?)
• The complexity of evaluating interpolation polynomials
• Quiz games as a model for information hiding
• On the bit complexity of polynomial system solving
• scientific article; zbMATH DE number 421669 (Why is no real title available?)
• In memoriam. Succinct obituary in memoriam of Joos Heintz

Describes a project that uses

Uses Software

• Eiffel

This page was built for publication: Lower complexity bounds for interpolation algorithms

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