  We present randomized algorithms to compute the sumset (Minkowski sum) of two
integer sets, and to multiply two univariate integer polynomials given by
sparse representations. Our algorithm for sumset has cost softly linear in the
combined size of the inputs and output. This is used as part of our sparse
multiplication algorithm, whose cost is softly linear in the combined size of
the inputs, output, and the sumset of the supports of the inputs. As a
subroutine, we present a new method for computing the coefficients of a sparse
polynomial, given a set containing its support. Our multiplication algorithm
extends to multivariate Laurent polynomials over finite fields and rational
numbers. Our techniques are based on sparse interpolation algorithms and
results from analytic number theory.
