Output-sensitive algorithms for sumset and sparse polynomial multiplication

Andrew Arnold, Daniel S. Roche

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…