Interpolation of sparse rational functions without knowing bounds on exponents
Dima Yu. Grigoriev, Marek Karpiński, Michael F. Singer · 2002
The authors present the first algorithm for the (black box) interpolation of t-sparse, n-variate, rational functions without knowing bounds on exponents of their sparse representation, with the number of queries independent of exponents. In fact, the algorithm uses O(nt/sup t/) queries to the black box, and it can be implemented for a fixed t in a polynomially bounded storage (or polynomial parallel time).>