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.
Type de document :
Communication dans un congrès
ISSAC - 39th International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. pp. 272-279, 2014, 〈10.1145/2608628.2608660〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01068308
Contributeur : Clément Pernet <>
Soumis le : jeudi 25 septembre 2014 - 14:01:39
Dernière modification le : jeudi 11 octobre 2018 - 08:48:03

Lien texte intégral

Identifiants

Citation

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, 2014, 〈10.1145/2608628.2608660〉. 〈hal-01068308〉

Partager

Métriques

Consultations de la notice

362