Atri Rudra

Algorithmic Coding theory

Abstract :

Error correcting codes systematically introduce redundancy into data so that the original information can be recovered when parts of the redundant data are corrupted. Error correcting codes are used ubiquitously in communication and data storage.

The main challenge in algorithmic coding theory is come up with good codes along with efficient encoding and decoding algorithms. By a good code we mean a code that has the potential to correct as many errors as possible (which can be corrected by an efficient decoding algorithm) while using as little redundancy as possible. Intuitively these are contradictory goals and meeting the optimal tradeoff between these two competitive goals is one of the central research endeavors in coding theory.

This survey begins with the classical results in this area dating back to the works of Shannon and Hamming and then gives a brief glimpse into three sub-fields in algorithmic coding theory that have seen a spurt of research activity in the last decade or so: