108 citations · 119 across the 5 of their papers we have counts for
Showing 2014Show all
3 papers · 1 filter
cs.SC2014★ 2 cited
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…
cs.SC2014
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…
cs.SC2014
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…