Abstract
In these two talks, we'll go over a prevalent paradigm in algorithm design for algebraic codes, based on interpolating and analyzing appropriate polynomials. In the first talk, we'll see three examples of this paradigm: The Berlekamp-Welch algorithm for uniquely decoding Reed-Solomon Codes; the Guruswami-Sudan Algorithm for list-decoding Reed-Solomon Codes; and the Guruswami-Wang algorithm for list-decoding Folded Reed-Solomon Codes. In the second talk, we'll discuss several techniques that can be used on top of this basic paradigm, including leveraging locality, distance amplification, and alphabet reduction. Throughout, we'll highlight several open problems!