Sparse polynomial interpolation with Bernstein polynomials

Abstract

We present an algorithm for interpolating an unknown univariate polynomial f that has a t sparse representation (t << deg(f) ) using Bernstein polynomials as term basis from 2t evaluations. Our method is based on manipulating given black box polynomial for f so that we can make use of Prony's algorithm.