108 citations · 119 across the 5 of their papers we have counts for
4 papers · 1 filter
Faster Sparse Multivariate Polynomial Interpolation of Straight-Line Programs
Andrew Arnold, Mark Giesbrecht, Daniel S. Roche
Given a straight-line program whose output is a polynomial function of the inputs, we present a new algorithm to compute a concise representation of that unknown function. Our algo…
Multivariate sparse interpolation using randomized Kronecker substitutions
Andrew Arnold, Daniel S. Roche
We present new techniques for reducing a multivariate sparse polynomial to a univariate polynomial. The reduction works similarly to the classical and widely-used Kronecker substit…
Sparse interpolation over finite fields via low-order roots of unity
Andrew Arnold, Mark Giesbrecht, Daniel S. Roche
We present a new Monte Carlo algorithm for the interpolation of a straight-line program as a sparse polynomial over an arbitrary finite field of size . We assume a priori bo…
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…