  Given a way to evaluate an unknown polynomial with integer coefficients, we
present new algorithms to recover its nonzero coefficients and corresponding
exponents. As an application, we adapt this interpolation algorithm to the
problem of computing the exact quotient of two given polynomials. These methods
are efficient in terms of the bit-length of the sparse representation, that is,
the number of nonzero terms, the size of coefficients, the number of variables,
and the logarithm of the degree. At the core of our results is a new Monte
Carlo randomized algorithm to recover a polynomial $f(x)$ with integer
coefficients given a way to evaluate $f(\theta) \bmod m$ for any chosen
integers $\theta$ and $m$. This algorithm has nearly-optimal bit complexity,
meaning that the total bit-length of the probes, as well as the computational
running time, is softly linear (ignoring logarithmic factors) in the bit-length
of the resulting sparse polynomial. To our knowledge, this is the first sparse
interpolation algorithm with soft-linear bit complexity in the total output
size. For polynomials with integer coefficients, the best previously known
results have at least a cubic dependency on the bit-length of the exponents.
