Multiplicity Codes

Abstract:

Multiplicity codes are natural error-correcting codes based on evaluations of polynomials and their derivatives. In many ways they have nicer properties than the classical polynomial-based Reed-Solomon codes and Reed-Muller codes. Multiplicity codes can have arbitrarily high rate, while simultaneously allowing for sublinear time decoding from errors. They also admit powerful list-decoding algorithms, achieving the so-called list-decoding capacity. I will talk about these codes and their decoding algorithms.

Part of this talk is based on joint work with Shubhangi Saraf and Sergey Yekhanin.