Sparse Polynomial Interpolation Based on Derivative

DOI10.1016/J.JSC.2022.06.002MaRDI QIDQ6334476arXivFDO

Authors Qiao-Long Huang

Publication date 21 January 2020

Mathematics Subject Classification ID

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

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).

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)