Computational Complexity of Sparse Rational Interpolation

DOI10.1137/S0097539791194069MaRDI QIDQ4286224zbMATH OpenFDO

Authors Michael F. Singer, Dima Grigoriev, Marek Karpinski

Publication date 27 April 1994

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539791194069

zbMATH Keywords

arithmetic operationscomputational complexityinterpolationsparse rational functions

Mathematics Subject Classification ID

Real rational functions (26C15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Cited in

(16)

• Computability of the additive complexity of algebraic circuits with root extracting
• Zero testing of \(p\)-adic and modular polynomials
• Early termination in sparse interpolation algorithms
• Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases
• Sparse shifts for univariate polynomials
• Lower complexity bounds for interpolation algorithms
• Noisy interpolation of sparse polynomials in finite fields
• Reconstructing rational functions with \texttt{FireFly}
• Computing Sparse Representations of Systems of Rational Fractions
• scientific article; zbMATH DE number 421669 (Why is no real title available?)
• A Wronskian approach to the real \(\tau\)-conjecture
• scientific article; zbMATH DE number 917814 (Why is no real title available?)
• Interpolation of dense and sparse rational functions and other improvements in \texttt{FireFly}
• Balancing act: multivariate rational reconstruction for IBP
• Sparse interpolation of multivariate rational functions
• Deterministically testing sparse polynomial identities of unbounded degree

This page was built for publication: Computational Complexity of Sparse Rational Interpolation

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