Adaptive decoding for dense and sparse evaluation/interpolation codes

We will present recent work on evaluation-interpolation error correcting codes. It is motivated in the study of algorithm based fault tolerance (ABFT) applied to parallel exact linear algebra. Indeed evaluation/interpolation schemes allow to split the computational load of one problem into several independent tasks, making the problem embarassingly parrallel. In the context where soft-errors occur during the computation of some of these tasks, the evaluation/interpolation codes make it possible to still recover the result provided that some amount of redundant information has been computed.

In a first part we will focus on the interpolation of dense polynomials with errors, and their equivalent over the ring of integer : the CRT-codes (Chinese Remainder Theorem). We will introduce a more general error model allowing to derive tighter bounds on the error correction capacities of such codes. Then we will describe some improvements making the error correction capacity adaptive with respect to the exact amount of information of the result to be computed.

In a second part we will focus on the interpolation of sparse polynomials with errors. After proving a lower bound on the required evaluation points, we will present a unique decoding algorithm matching that bound and a list-decoding variant of it, with a lesser requirement on the number of evaluations.