Traditionally, algorithms for univariate polynomials have been
studied when the input polynomials are given in a dense form, as a
vector of all coefficients. More recent work has focused on the
*supersparse* representation of a polynomial by a list of pairs
of nonzero coefficients and their corresponding exponents. In fact,
studying algorithms for the supersparse representation is an
important practical issue, as this is the way polynomials are
represented by default in most computer algebra systems such as
Maple and Mathematica.

We give new algorithms for two important problems when the input is
given as a supersparse polynomial. First, we give an algorithm to
interpolate an unknown integer polynomial in the sparsest shifted
power basis, given a method or *black box* for evaluating that
polynomial at a point modulo a prime. Second, the question of
decomposing a univariate polynomial is investigated when the input
is supersparse, with a few elementary hardness results, as well as
new algorithms to compute sparse decompositions. Some interesting
connections are noted to long-standing open problems studied by
Erdös, Schinzel and others.