Algorithmic decoding is the problem of efficiently decoding a corrupted received word, to obtain the closest codeword or a list of all nearby codewords. An error-correcting code, however theoretically good, is only of practical use if it has _efficient_ decoding algorithms. In this talk I will describe efficient decoding algorithms for several algebraic codes and expander codes.
Multivariate Multiplicity codes are a generalisation of Reed-Muller codes, where along with evaluations of a multivariate polynomial, evaluations of its partial derivatives are also given, up to some order. The main result of this portion is a general algorithm to unique-decode this code for _all_ choices of field, dimension and multiplicity parameter. Hence, it is also an algorithmic proof of the Multiplicity Schwartz-Zippel lemma.
Univariate Multiplicity codes are an extension of Reed-Solomon codes where evaluations of a univariate polynomial along with its derivatives are given. The main result of this section is a way to make the Guruswami-Wang list decoding algorithm run in nearly linear time. For this, we have to speed up both steps of Guruswami-Wang: constructing the differential equation and solving it. We also generalise our fast list-decoding algorithm to the case of list recovery.
Local testing is the problem of querying a few locations to distinguish whether a received word is a codeword or _far_ from all codewords. Many known local tests (the low-degree tests of Friedl-Sudan and Raz-Safra, for instance) have the property that they work for the interleaved version of their codes as well. This can be seen by looking into their proofs. We show that this is in fact a general property of locally testable codes, if the underlying test graph is a good expander. On the way, we also give a stronger definition of local testability that may be of independent interest.
Finally, we give a simple algorithm to decode Sipser-Spielman expander codes, that approaches closer to the unique-decoding bound than Sipser and Spielman's original algorithm.