Sparse interpolation is the task of learning the sparse representation of a polynomial, given a way to evaluate it at chosen points. Compared to standard (dense) interpolation, the goal is to use a number of evaluations points that is linear in the number of nonzero monomials rather than the degree. This problem has a rich history due to its relevance for polynomial factorization, system solving or more recently sparse polynomial arithmetic.
In my talk, I will present the main approaches for sparse interpolation and show how to combine them to get a quasi-linear time algorithm for polynomials with integer coefficients. In particular, I will describe how to handle the case of unbalanced polynomials where the bit-lengths of the coefficients may vary widely. As an application, these techniques provide an efficient algorithm to multiply two unbalanced integer polynomials. This provides a quasi-linear time algorithm where the standard methods can become quadratic in the most unfavorable cases.
My talk is based on joint works with Pascal Giorgi, Armelle Perret du Cray and Daniel S. Roche.
