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 my thesis I describe efficient decoding algorithms for several algebraic codes and expander codes.
I will describe (1) A unique-decoding algorithm for Multivariate Multiplicity codes, (2) Algorithms for list-decoding and list-recovery of Univariate Multiplicity codes that run in nearly linear time, and (3) A simple algorithm to decode Sipser-Spielman codes approaching the unique-decoding radius. The techniques used include tools from algebra and combinatorics.
