Sparse Representations of Polynomials

Dr. Erdal Imamoğlu

04 February 2022 17:00

Abstract

Univariate sparse polynomial interpolation is the process of reconstructing an unknown polynomial f from given a way to evaluate f at a chosen point, an upper bound on the degree of f, and an upper bound on the number of nonzero terms of f. Algorithms for interpolating an unknown polynomial that has a sparse representation in the standard power basis dates back to the 18th century and it is rediscovered in 1980s. Within the last years, algorithms for interpolating an unknown polynomial that has a sparse representation in a basis different than the standard basis are developed. In this talk, we present methods to interpolate an unknown polynomial that has a sparse representation in terms of Chebyshev polynomials, Dickson polynomials of the (k+1)-th kind, or Bernstein polynomials.