In this paper, we consider the problem of efficient computations with structured polynomials. We provide complexity results for computing Fourier Transform and Truncated Fourier Transform of symmetric polynomials, and for multiplying polynomials supported on a lattice.

Authors: Joris van der Hoeven, Romain Lebreton Éric Schost

Keywords: FFT, TFT, symmetric polynomials, algorithm, complexity

View: Html, TeXmacs, Pdf, BibTeX