Computational Complexity of Sparse Rational Interpolation
From MaRDI portal
Publication:4286224
DOI10.1137/S0097539791194069zbMath0802.68060MaRDI QIDQ4286224
Marek Karpinski, Michael F. Singer, Dima Yu. Grigoriev
Publication date: 27 April 1994
Published in: SIAM Journal on Computing (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68W30: Symbolic computation and algebraic computation
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
26C15: Real rational functions
Related Items
Sparse interpolation of multivariate rational functions, Deterministically testing sparse polynomial identities of unbounded degree, 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, Noisy interpolation of sparse polynomials in finite fields