Sparse Polynomial Interpolation with Finitely Many Values for the Coefficients
Lists
Only you see this
Abstract
In this paper, we give new sparse interpolation algorithms for black box polynomial f whose coefficients are from a finite set. In the univariate case, we recover f from one evaluation $$f(\beta )$$ for a sufficiently large number $$\beta $$ . In the multivariate case, we introduce the modified Kronecker substitution to reduce the interpolation of a multivariate polynomial to that of the univariate case. Both algorithms have polynomial bit-size complexity.
BibTeX
@inproceedings{huang2017sparse,
author = {Qiao-Long Huang and Xiao-Shan Gao},
title = {{Sparse Polynomial Interpolation with Finitely Many Values for the Coefficients}},
booktitle = {CASC},
year = {2017},
doi = {10.1007/978-3-319-66320-3\_15},
}Loading related content...