On the decidability of sparse univariate polynomial interpolation

Abstract

We consider the problem of determining whether or not there exists a sparse univariate polynomial that interpolates a given set S={(xi, yi)} of points. Several important cases are resolved, e.g., the case when the xi's are all positive rational numbers. But the general problem remains open. © 1991 Birkhäuser Verlag.