Highlights of Algorithmic Coding Theory

Madhu Sudan (Harvard University)

In this series of talks, we will quickly introduce the mathemtical notions of an error-correcting code, and the associated notions of Encoding and Decoding Algorithms. After reviewing some of the classical results on the existence, construction and limits on error-correcting codes, we will zoom in on two results in the field. 
1) The construction of capacity achieving codes (based on Folded Reed Solomon Codes) over large alphabets and their encoding and decoding: Given any error parameter delta in [0,1] and epsilon > 0, these codes achieve a rate 1-delta-epsilon and correct delta fraction of adversarial errors with alphabet size growing only with epsilon. 
2) The construction of binary error correcting codes (Polar codes) that achieve Shannon capacity at small block lengths: I.e, given delta in [0,1/2] and epsilon > 0 correct delta fraction of random errors with rate 1- h(delta) - epsilon at lengths poly(1/epsilon). [Here h(p) = -p log_2 p - (1-p) log_2 (1-p) is the binary entropy function].
Both results come with polynomial time algorithms!