A deterministic algorithm for sparse multivariate polynomial interpolation
Michael Ben-Or · 1988
An efficient deterministic polynomial time algorithm is developed for the sparse polynomial interpolation problem. The number of evaluations needed by this algorithm is very small. The algorithm also has a simple NC implementation.