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

Wednesday January 9th, 2013, 12:30pm, K9509.

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.