Revisit Randomized Kronecker Substitution based Sparse Polynomial Interpolation
share
In this paper, a new Monte Carlo interpolation algorithm for sparse multivariate polynomials is given based on the idea of randomized Kronecker substitution. The main contribution is a new method to reduce multivariate polynomial interpolation to that of univariate polynomials, which leads to better computational complexities. For an n-variate black-box polynomial f with a degree bound D and a term bound T, if the coefficients of f are taken from an integral domain R, the algorithm needs O^(nTD) evaluations plus O^(nTD) R operations. If the coefficients of f are taken from a finite field F_q, the algorithm needs O^(nT) evaluations plus O^(nTD q) bit operations. This is the first reduction based algorithm whose complexity is linear in n,T,D, q.
READ FULL TEXT