Computational Complexity of Sparse Rational Interpolation
From MaRDI portal
Publication:4286224
DOI10.1137/S0097539791194069zbMath0802.68060MaRDI QIDQ4286224
Michael F. Singer, Dima Yu. Grigoriev, Marek Karpinski
Publication date: 27 April 1994
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Real rational functions (26C15)
Related Items
Early termination in sparse interpolation algorithms ⋮ Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases ⋮ Computability of the additive complexity of algebraic circuits with root extracting ⋮ Sparse shifts for univariate polynomials ⋮ 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 ⋮ Reconstructing rational functions with \texttt{FireFly} ⋮ A Wronskian approach to the real \(\tau\)-conjecture ⋮ Deterministically testing sparse polynomial identities of unbounded degree ⋮ Noisy interpolation of sparse polynomials in finite fields ⋮ Zero testing of \(p\)-adic and modular polynomials
