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 …

In the sparse polynomial multiplication problem, one is asked to multiply two sparse
polynomials f and g in time that is proportional to the size of the input plus the size of the …

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 probabilistic algorithm to compute the product of two univariate sparse
polynomials over a field with a number of bit operations that is quasi-linear in the size of the …

The demand for processing vast volumes of data has surged dramatically due to the
advancement of machine learning technology. Large-scale data processing necessitates …

In this article, we study the problem of multiplying two multivariate polynomials which are
somewhat but not too sparse, typically like polynomials with convex supports. We design …

La manipulation de polynômes est une étape souvent incontournable, que ce soit pour la
résolution de problèmes théoriques ou pour la modélisation du monde physique. Dans le …

Computing the convolution A⋆ B of two length-n vectors A, B is an ubiquitous computational
primitive, with applications in a variety of disciplines. Within theoretical computer science …

We consider the classical problems of interpolating a polynomial given a black box for
evaluation, and of multiplying two polynomials, in the setting where the bit-lengths of the …

Structured FFT and TFT Page 1 ∗ Joris van der Hoeven Laboratoire d’informatique UMR
7161 CNRS École 91128 Palaiseau Cedex, France vdhoeven@lix.polytechnique.fr Romain …