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

International audienceThis 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