  We consider the problem of interpolating an unknown multivariate polynomial
with coefficients taken from a finite field or as numerical approximations of
complex numbers. Building on the recent work of Garg and Schost, we improve on
the best-known algorithm for interpolation over large finite fields by
presenting a Las Vegas randomized algorithm that uses fewer black box
evaluations. Using related techniques, we also address numerical interpolation
of sparse polynomials with complex coefficients, and provide the first provably
stable algorithm (in the sense of relative error) for this problem, at the cost
of modestly more evaluations. A key new technique is a randomization which
makes all coefficients of the unknown polynomial distinguishable, producing
what we call a diverse polynomial. Another departure from most previous
approaches is that our algorithms do not rely on root finding as a subroutine.
We show how these improvements affect the practical performance with trial
implementations.
