Faster sparse interpolation of straight-line programs

Andrew Arnold, Mark Giesbrecht, Daniel S. Roche

We give a new probabilistic algorithm for interpolating a "sparse" polynomial f given by a straight-line program. Our algorithm constructs an approximation f* of f, such that their…