  In this paper, we propose two new interpolation algorithms for sparse
multivariate polynomials represented by a straight-line program(SLP). Both of
our algorithms work over any finite fields $F_q$ with large characteristic. The
first one is a Monte Carlo randomized algorithm. Its arithmetic complexity is
linear in the number $T$ of non-zero terms of $f$, in the number $n$ of
variables. If $q$ is $O((nTD)^{(1)})$, where $D$ is the partial degree bound,
then our algorithm has better complexity than other existing algorithms. The
second one is a deterministic algorithm. It has better complexity than existing
deterministic algorithms over a field with large characteristic. Its arithmetic
complexity is quadratic in $n,T,\log D$, i.e., quadratic in the size of the
sparse representation. And we also show that the complexity of our
deterministic algorithm is the same as the one of deterministic zero-testing of
Bl\"{a}ser et al. for the polynomial given by an SLP over finite field (for
large characteristic).
