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