  In this paper, we propose new deterministic and Monte Carlo interpolation
algorithms for sparse multivariate polynomials represented by straight-line
programs. Let $f$ be an $n$-variate polynomial given by a straight-line
program, which has a degree bound $D$ and a term bound $T$. Our deterministic
algorithm is quadratic in $n,T$ and cubic in $\log D$ in the Soft-Oh sense,
which has better complexities than existing deterministic interpolation
algorithms in most cases. Our Monte Carlo interpolation algorithms have better
complexities than existing Monte Carlo interpolation algorithms and are the
first algorithms whose complexities are linear in $nT$ in the Soft-Oh sense.
Since $nT$ is a factor of the size of $f$, our Monte Carlo algorithms are
optimal in $n$ and $T$ in the Soft-Oh sense.
