Consider a sparse multivariate polynomial with integer coefficients. Assume that is represented as a “modular black box polynomial”, e.g. via an algorithm to evaluate at arbitrary integer points, modulo arbitrary positive integers. The problem of sparse interpolation is to recover in its usual sparse representation, as a sum of coefficients times monomials. For the first time we present a quasi-optimal algorithm for this task.

Authors: Joris van der Hoeven, Grégoire Lecerf

View: Html, TeXmacs, Pdf, BibTeX