Sparse Polynomial Interpolation.

Andrew Arnold, University of Waterloo

11:30am, Tuesday September 2nd, 2014, K9509.

Abstract


Polynomial interpolation is the problem of reconstructing a polynomial from a
set of its evaluations or modular images. Polynomial interpolation is a
fundamental tool of computer algebra and has applications to power series,
polynomial, and integer arithmetic.

We consider the problem of interpolating a polynomial that is sparse, i.e., a
polynomial with only a small number of nonzero terms, such that the true "size"
of the polynomial is much smaller than its degree.  In this talk we discuss
recently-developed randomized techniques for interpolating sparse polynomials,
with different methods to handle the cases of univariate, bivariate, and
higher-dimensional multivariate polynomials.  This is joint work with Mark
Giesbrecht and Daniel Roche.