Computational Complexity of Sparse Rational Interpolation

TitleComputational Complexity of Sparse Rational Interpolation
Publication TypeTechnical Report
Year of Publication1991
AuthorsGrigoriev, D. Yu., Karpinski M., & Singer M. F.
Other Numbers648
KeywordsAlgorithms, Arithmetic Complexity, Computational Complexity, Sparse Rational Interpolation

We analyze the computational complexity of sparse rational interpolation, and give the first genuine time (arithmetic complexity does not depend on the size of the coefficients) algorithm for this problem.

Bibliographic Notes

ICSI Technical Report TR-91-018

Abbreviated Authors

D. Grigoriev, M. Karpinski, and M. F. Singer

ICSI Publication Type

Technical Report