A recursive, Las Vegas algorithm for the interpolation of sparse polynomials given by straight-line programs
Andrew Arnold, School of Computing Science, University of Waterloo
Abstract: We present a recursive algorithm to interpolate a t-sparse univariate polynomial of degree d given by a straight-line program. We show, in addition, how this algorithm may be used to interpolate black-box polynomials with real or complex-valued coefficients using soft-O( t log^3 d) probes. This work builds on ideas from previous algorithms by Garg and Schost, and by Giesbrecht and Roche.