White-box sparse interpolation Let $C$ be an arithmetic circuit that represents a polynomial $f\in\mathbb K[x_1,\dotsc,x_n]$, with the promise that $f$ has at most $k$ nonzero terms. What is (known about) the complexity of computing $f$ in its sparse representation, given $C$?

I am interested in deterministic and randomized complexity, and in the link with PIT. In particular, does the promise that $f$ is sparse imply good algorithms? A priori, I am more interested in the case of $\mathbb K$ being some finite field, though results over other fields may be relevant.
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.