Skip to Main content Skip to Navigation
Conference papers

Sparse Polynomial Interpolation Codes and their decoding beyond half the minimal distance

Erich L. Kaltofen 1 Clément Pernet 2, 3 
2 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
3 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We present algorithms performing sparse univariate polynomial interpolation with errors in the evaluations of the polynomial. Based on the initial work by Comer, Kaltofen and Pernet [Proc. ISSAC 2012], we define the sparse polynomial interpolation codes and state that their minimal distance is precisely the length divided by twice the sparsity. At ISSAC 2012, we have given a decoding algorithm for as much as half the minimal distance and a list decoding algorithm up to the minimal distance. Our new polynomial-time list decoding algorithm uses sub-sequences of the received evaluations indexed by a linear progression, allowing the decoding for a larger radius, that is, more errors in the evaluations while returning a list of candidate sparse polynomials. We quantify this improvement for all typically small values of number of terms and number of errors, and provide a worst case asymptotic analysis of this improvement. For instance, for sparsity T = 5 with up to 10 errors we can list decode in polynomial-time from 74 values of the polynomial with unknown terms, whereas our earlier algorithm required 2T (E + 1) = 110 evaluations. We then propose two variations of these codes in characteristic zero, where appropriate choices of values for the variable yield a much larger minimal distance: the length minus twice the sparsity.
Complete list of metadata
Contributor : Clément Pernet Connect in order to contact the contributor
Submitted on : Thursday, September 25, 2014 - 2:01:39 PM
Last modification on : Wednesday, July 6, 2022 - 4:14:07 AM

Links full text




Erich L. Kaltofen, Clément Pernet. Sparse Polynomial Interpolation Codes and their decoding beyond half the minimal distance. ISSAC - 39th International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. pp. 272-279, ⟨10.1145/2608628.2608660⟩. ⟨hal-01068308⟩



Record views