On the bit complexity of sparse integer polynomial interpolation.

Andrew Arnold, University of Waterloo

10:30am Tuesday February 17th, 2015, in K9509.

Abstract

We consider the multiplication of polynomials with integer coefficients,
given by sparse representations.  For this problem the number of terms in
the output can greatly vary from quadratic to constant with respect to the
number of terms in the inputs, depending on the cancellation of terms.  In
the event that the output has very few terms, grade-school multiplication
may have cost potentially quadratic with respect to the total size of the
inputs and output.  We present a probabilistic multiplication algorithm for
sparse polynomials that, assuming a naive height bound on the output, is
softly linear with respect to the combined bit size of the inputs and
output.  This algorithm is based off of techniques developed for sparse
interpolation of straight-line programs.  

This is joint work with Dan Roche of the United States Naval Academy.