Sparse Polynomial Interpolation Based on Derivative

DOI10.1016/J.JSC.2022.06.002arXiv2002.03708MaRDI QIDQ6334476FDOQ6334476

Authors: Qiao-Long Huang 

Publication date: 21 January 2020

Abstract: In this paper, we propose two new interpolation algorithms for sparse multivariate polynomials represented by a straight-line program(SLP). Both of our algorithms work over any finite fields $F_q$ with large characteristic. The first one is a Monte Carlo randomized algorithm. Its arithmetic complexity is linear in the number $T$ of non-zero terms of $f$, in the number $n$ of variables. If $q$ is $O((nTD{)}^{(1)})$, where $D$ is the partial degree bound, then our algorithm has better complexity than other existing algorithms. The second one is a deterministic algorithm. It has better complexity than existing deterministic algorithms over a field with large characteristic. Its arithmetic complexity is quadratic in $n,T,logD$, i.e., quadratic in the size of the sparse representation. And we also show that the complexity of our deterministic algorithm is the same as the one of deterministic zero-testing of Bl"{a}ser et al. for the polynomial given by an SLP over finite field (for large characteristic).

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Numerical approximation and computational geometry (primarily algorithms) (65Dxx) Computational number theory (11Yxx)

This page was built for publication: Sparse Polynomial Interpolation Based on Derivative

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6334476)