We present the open-source C++ library FireFly for the reconstruction of multivariate rational
functions over finite fields. We discuss the involved algorithms and their implementation. As …

We present the main improvements and new features in version 2.0 of the open-source C++
library FireFly for the interpolation of rational functions. This includes algorithmic …

Simply put, a sparse polynomial is one whose zero coefficients are not explicitly stored.
Such objects are ubiquitous in exact computing, and so naturally we would like to have …

Consider the black box interpolation of a τ-sparse, n-variate rational function f, where τ is the
maximum number of terms in either numerator or denominator. When numerator and …

We present randomized algorithms to compute the sumset (Minkowski sum) of two integer
sets, and to multiply two univariate integer polynomials given by sparse representations. Our …

We present a parallel GCD algorithm for sparse multivariate polynomials with integer
coefficients. The algorithm combines a Kronecker substitution with a Ben-Or/Tiwari sparse …

Given a straight-line program whose output is a polynomial function of the inputs, we present
a new algorithm to compute a concise representation of that unknown function. Our …

Given a way to evaluate an unknown polynomial with integer coefficients, we present new
algorithms to recover its nonzero coefficients and corresponding exponents. As an …

We consider the problem of interpolating an unknown multivariate polynomial with
coefficients taken from a finite field or as numerical approximations of complex numbers …

In this paper, we propose a new interpolation algorithm for a sparse multivariate polynomial
represented by a straight-line program (SLP). Our algorithm is a Monte Carlo randomized …