Towards faster practical sparse polynomial interpolation.

Joris van der Hoven, Laboratoire d'informatique de l'École polytechnique, Paris.

Tuesday December 3rd, 9:30am in AQ 5004.

Abstract:

Consider a program f(x1,...,xn) that actually computes
a sparse polynomial in x1,...,xn.  The problem of sparse polynomial
interpolation consists of determining this polynomial in its usual
representation from the evaluations of f at sufficiently many
well chosen points.

In our talk, we will survey various approaches to solve this problem.
We mainly focus on possibly heuristic algorithms that are most efficient
in practice and on the particular case when f has coefficients in
a finite field.