Fast Interpolation Algorithms for Sparse Polynomials with Respect to the Size of Coefficients
Alexander L. Chistov, Marek Karpiński · 1994
In this paper we consider the interpolation of sparse polynomials in two different oracle models taking into account the size of coefficients only. St. Petersburg Institute for Informatics and Automation of the Academy of Sciences of Russia, and Department of Computer Science, University of Bonn, 53117 Bonn. Research supported by the Volkswagen--Stiftung, Program on Computational Complexity. y Department of Computer Science, University of Bonn, 53117 Bonn, and International Computer Science Institute, Berkeley, California, E Mail: [email protected]. Research supported in part by the DFG Grant KA 673/4--1, by the ESPRIT BR Grants 7097 and ECU030, and by the Volkswagen--Stiftung. Introduction The models considered so far require exact computations, see [3],[4],[5], but in practice exact computations of values of sparse polynomials are very difficult. Indeed, we cannot even compute values of sparse polynomials in small integer points such as 2,3,: : : . Since the lengths of the ...