White-box sparse interpolation
There are deterministic and randomized algorithm running in time $\mathrm{poly}(n,d,k)$, where $n$ is the number of variables, $d$ is the degree and $k$ is the sparsity. AFAIK, the results are stated for characteristic zero fields but work over any field large enough (again, polynomially large in the parameters). 

This paper of Kaltofen and Yagati discusses both the randomized algorithm of Zippel and the deterministic algorithm of Ben-Or and Tiwari, and then goes on to present some improvements.