Interpolating Polynomials from Their Values

Abstract

A fundamental technique used by many algorithms in computer algebra is interpolating polynomials from their values. This paper discusses two algorithms for solving this problem for sparse multivariate polynomials, an updated version of a probabilistic one and a new deterministic technique that uses some ideas due to Ben-Or and Tiwari (1988). In addition, algorithms are presented for quickly finding points that are not zeroes of sparse multivariate polynomials - the zero avoidance problem.