Lower complexity bounds for interpolation algorithms

DOI10.1016/J.JCO.2010.10.003zbMATH Open1277.65008OpenAlexW1999337317MaRDI QIDQ2431336FDOQ2431336

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

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
• 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

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)

Cites Work

• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Model Theory
• Title not available (Why is that?)
• The red book of varieties and schemes
• The hardness of polynomial equation solving
• Generic local structure of the morphisms in commutative algebra
• Kronecker's smart, little black boxes
• Title not available (Why is that?)
• Title not available (Why is that?)
• On multivariate polynomial interpolation
• On the intrinsic complexity of elimination theory
• On Multivariate Interpolation
• Title not available (Why is that?)
• Title not available (Why is that?)
• The least solution for the polynomial interpolation problem
• Title not available (Why is that?)
• A continuity property of multivariate Lagrange interpolation
• Constraint Databases
• Title not available (Why is that?)

Cited In (6)

• On the bit complexity of polynomial system solving
• Quiz games as a model for information hiding
• Title not available (Why is that?)
• The complexity of evaluating interpolation polynomials
• In memoriam. Succinct obituary in memoriam of Joos Heintz
• Title not available (Why is that?)

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)