Polynomial Linear System Solving with Random Errors: New Bounds and Early Termination Technique

Eleonora Guerrini (1) , Romain Lebreton (1) , Ilaria Zappatore (2)

1 ECO - Exact Computing
2 GRACE - Geometry, arithmetic, algorithms, codes and encryption

This paper deals with the polynomial linear system solving with errors (PLSwE) problem. More specifically, we solve linear systems with univariate polynomial coefficients via an evaluationinterpolation technique assuming that errors can occur before the interpolation step. In this framework, the number of evaluations needed to recover the solution depends on the parameters of the linear system (degrees, size) and on the number of errors. Our work is part of a series of papers about PLSwE aiming to reduce this number of evaluations, which is crucial since it affects the complexity. We proved in [7] that if errors are randomly distributed, the bound on the number of evaluations can be lowered with respect to the error rate. In this paper, following the approach of [9], we improve the results of [7] in two directions. First, we propose a new bound on the number of evaluations, lowering the dependency on the parameters of the linear system, based on the work of [5]. Second, we introduce an early termination strategy in order to handle the unnecessary increase of the number of evaluations due to the overestimation of the output degrees and of the number of errors.

Mots clés: Polynomial linear system solving; interleaved Reed Solomon codes; simultaneous rational function reconstruction

Domaines: Calcul formel [cs.SC]

Eleonora Guerrini, Romain Lebreton, Ilaria Zappatore. Polynomial Linear System Solving with Random Errors: New Bounds and Early Termination Technique. ISSAC 2021 - 46th International Symposium on Symbolic and Algebraic Computation, Jul 2021, Saint Petersburg, Russia. pp.171-178, ⟨10.1145/3452143.3465548⟩. ⟨hal-03386106⟩