Séminaire Calcul Formel

Simultaneous Rational Function Reconstruction and applications to Algebraic Coding Theory

by Dr Ilaria Zappatore (Inria Saclay)




The simultaneous rational function reconstruction (SRFR) is the problem of reconstructing a vector of rational functions with the same denominator given its evaluations (or more generally given its remainders modulo different polynomials). The peculiarity of this problem consists in the fact that the common denominator constraint reduces the number of evaluation points needed to guarantee the existence of a solution, possibly losing the uniqueness.

One of the main contributions presented in this talk consists in the proof that uniqueness is guaranteed for almost all instances of this problem. This result was obtained by elaborating some other contributions and techniques derived by the applications of SRFR, from the polynomial linear system solving to the decoding of Interleaved Reed-Solomon codes.

In this talk it is also presented another application of the SRFR problem, concerning the problem of constructing fault-tolerant algorithms: algorithms resilient to computational errors.

These algorithms are constructed by introducing redundancy and using error correcting codes tools to detect and possibly correct errors which occur during computations. In this application context, we improve an existing fault-tolerant technique for polynomial linear system solving by evaluation-interpolation, by focusing on the related SRFR.

Contains joint works with Eleonora Guerrini and Romain Lebreton.