ALCYON lab

ALgorithms for
Combinatorics,
geometrY,
Optimization and
Number theory
Home Members Projects Publications SCIM Theses topics

Sparse Representations of Polynomials


Dr. Erdal Imamoğlu


Kırklareli University

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.