Sparse polynomial interpolation based on derivatives. (January 2023) - Huang, Qiao-Long
Abstract: We propose two new interpolation algorithms for sparse multivariate polynomials represented by a straight-line program (SLP). Both of our algorithms work over any finite fields F q with large characteristic. The first algorithm is randomized of the Monte Carlo type. Its bit complexity is linear in the number of non-zero terms T and the number of variables n of f . Let D be the partial degree bound of f . If q is in O ( ( n T D ) ( 1 ) ), our algorithm has better complexity than other existing algorithms. The second algorithm is deterministic; it has better complexity than any existing deterministic algorithms in the field with large characteristic. Its bit complexity is quadratic in n, T, log ⁡ D .