Andrew Arnold, U Waterloo
A recursive, Las Vegas algorithm for the interpolation of sparse polynomials given by straight-line programs
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.
No recent activity
Smith Hall, University of Delaware, Newark, DE 19716, USAEnlarge Map