Sparse Polynomial Interpolation over Fields with Large or Zero Characteristic
Qiao-Long Huang · 2019
In this paper, we propose a new interpolation algorithm for a sparse multivariate polynomial represented by a straight-line program (SLP). Our algorithm is a Monte Carlo randomized algorithm and works over fields with large or zero characteristic. Let f be an n-variate polynomial given by a straight-line program, which has a degree bound D and a term bound T. For fields of large characteristic, the bit complexity of our algorithm is linear in n,T,łog D in the Soft-Oh sense. Since n,T,łog D are factors of the size of f, our algorithm is optimal in n,T and łog D in the Soft-Oh sense. For fields of characteristic 0, the arithmetic complexity of our algorithm is also linear in n,T,łog D in the Soft-Oh sense. But the arithmetic complexity does not account for coefficient growth and therefore might be a poor reflection of reality.