Consider a multivariate polynomial \(f \in K [x_1, \ldots , x_n]\) over a field K, which is given through a black box capable of evaluating f at points in \(K^n\) , or possibly at points in \(A^n\) for any K-algebra A. The problem of sparse interpolation is to express f in its usual form with respect to the monomial basis. We analyze the complexity of various old and new algorithms for this task in terms of bounds D and T for the total degree of f and its number of terms. We mainly focus on the case when K is a finite field and explore possible speed-ups.
