Computational Complexity of Sparse Rational Interpolation
- 1 February 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 23 (1) , 1-11
- https://doi.org/10.1137/s0097539791194069
Abstract
The authors analyze the computational complexity of sparse rational interpolation, and give the first deterministic algorithm for this problem with singly exponential bounds on the number of arithmetic operations.Keywords
This publication has 15 references indexed in Scilit:
- Complexity of quantifier elimination in the theory of algebraically closed fieldsPublished by Springer Nature ,2005
- Interpolation of sparse rational functions without knowing bounds on exponentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The interpolation problem for k-sparse sums of eigenfunctions of operatorsAdvances in Applied Mathematics, 1991
- Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite FieldsSIAM Journal on Computing, 1990
- Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fieldsJournal of Pure and Applied Algebra, 1990
- Complexity of deciding Tarski algebraJournal of Symbolic Computation, 1988
- Solving systems of polynomial inequalities in subexponential timeJournal of Symbolic Computation, 1988
- Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential timeJournal of Mathematical Sciences, 1986
- Factorization of polynomials over a finite field and the solution of systems of algebraic equationsJournal of Mathematical Sciences, 1986
- Generalized Vandermonde determinants and roots of unity of prime orderProceedings of the American Mathematical Society, 1976