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.
Many algorithms have been designed, depending on the input representation (black-box or arithmetic circuit for instance) and the ring of coefficients. Black-box algorithms à la Prony reconstruct the polynomial from its evaluations on a geometric progression, and usually run in exponential time. Arithmetic-circuit algorithms à la Garg and Schost reconstruct the polynomial from its reductions modulo binomials, and have a polynomial-time complexity.
In a joint work with Pascal Giorgi, Armelle Perret du Cray and Daniel S. Roche, we combine both techniques to obtain the first quasi-linear time algorithm, that works for polynomials over the integers. In my talk, I will give an overview of the two main techniques, and then explain how we combined them to obtain our new algorithm.
