Institut für Informatik   Abteilung V

 Universität Bonn -> Institut für Informatik -> Abteilung V CS-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, 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  English Universität Bonn -> Institut für Informatik -> Abteilung V