Sparse polynomial interpolation with Bernstein polynomials

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. Scientific and Technological Research Council of Turkey (TUBTAK)Turkiye Bilimsel ve Teknolojik Arastirma Kurumu (TUBITAK) [119F426] The authors are supported by the Scientific and Technological Research Council of Turkey (TUBTAK) under Project 119F426.