Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1985-1989 Copyright 1985-1989 University of Bonn, Department of Computer Science, Abt. V
8539

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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V