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.