Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, Abt. V
893

Interpolation of Sparse Rational Functions without Knowing Bounds on Exponents
Dima Y. Grigoriev, Marek Karpinski, Michael Singer
[Download PostScript] [Download PDF]

We present the first algorithm for the ({\em black box\/}) interpolation of $t$-sparse, $n$-variate rational functions without knowing bounds on exponents of their sparse representation with the number of queries needed by the algorithm, independent on exponents. In fact, the algorithm uses $O(nt^t)$ queries to the {\em black box\/}, and can be implemented for a fixed $t$ in a polynomially bounded storage (or polynomial parallel time).

Last Change: 11/05/14 at 09:11:58
 English
Universität Bonn -> Institut für Informatik -> Abteilung V