Sparse polynomial interpolation: faster strategies over finite fields

Consider a multivariate polynomial f∈K[x1,…,xn] over a field K, which is given through a black box capable of evaluating f at points in Kn, or possibly at points in An 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.