In this paper, we propose new deterministic interpolation algorithms andMonte Carlo interpolation algorithms for sparse multivariate polynomialsrepresented by straight-line programs. Let f be an n-variate polynomial with adegree bound D and and term bound T. Our deterministic algorithms have bettercomplexities than existing deterministic interpolation algorithms in mostcases. Our Monte Carlo interpolation algorithms are asymptotically optimal inthe sense that their bit complexities are linear in nT and cubic in log D, whenthe coefficients of the polynomials are from a finite field. Since f has sizenT, our algorithm implies that interpolating a straight-line program polynomialf is as easy as reading f, if the log D factor in the complexities is notconsidered. Based on the Monte Carlo interpolation algorithm, we give anasymptotically optimal algorithm for the multiplication of several multivariatepolynomials, whose complexity is softly linear in the input size plus theoutput size, if the logarithm factors are ignored.
展开▼
