The complexity of evaluating interpolation polynomials

DOI10.1016/0304-3975(85)90078-7MaRDI QIDQ1081273zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1985

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(85)90078-7

zbMATH Keywords

complexity boundscoefficients of the Lagrangian interpolation polynomial

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical interpolation (65D05) Interpolation in approximation theory (41A05)

Recommendations

• Polynomial evaluation and interpolation on special sets of points
• Interpolation of polynomials given by straight-line programs
• Lower complexity bounds for interpolation algorithms
• On the complexities of multipoint evaluation and interpolation
• scientific article; zbMATH DE number 69493

Cites work

• scientific article; zbMATH DE number 3873251 (Why is no real title available?)
• scientific article; zbMATH DE number 3545079 (Why is no real title available?)
• scientific article; zbMATH DE number 3628385 (Why is no real title available?)
• scientific article; zbMATH DE number 3349977 (Why is no real title available?)
• A fast method for interpolation using preconditioning
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• The complexity of partial derivatives

Cited in

(14)

• Lagrange interpolation on a processor tree with ring connections
• scientific article; zbMATH DE number 917814 (Why is no real title available?)
• Semi-algebraic decision complexity, the real spectrum, and degree
• Interpolation cryptanalysis of unbalanced Feistel networks with low degree round functions
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• Lower complexity bounds for interpolation algorithms
• Combinatorial algorithms for the interpolation of polynomials in dimension \(\geq 2\)
• Complexity of interpolation and related problems in positive calculi
• Arithmetic complexity of the Stirling transforms
• On the complexities of multipoint evaluation and interpolation
• On the Complexity of the Interlace Polynomial
• scientific article; zbMATH DE number 421669 (Why is no real title available?)
• MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity
• Quantum cryptanalysis of Farfalle and (generalised) key-alternating Feistel networks

This page was built for publication: The complexity of evaluating interpolation polynomials

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