
A recursive, Las Vegas algorithm for the interpolation of sparse polynomials given by straightline programsAndrew Arnold, School of Computing Science, University of Waterloo
Abstract: We present a recursive algorithm to interpolate a tsparse univariate polynomial of degree d given by a straightline program. We show, in addition, how this algorithm may be used to interpolate blackbox polynomials with real or complexvalued coefficients using softO( t log^3 d) probes. This work builds on ideas from previous algorithms by Garg and Schost, and by Giesbrecht and Roche. 