Atri Rudra

List Decoding and Property Testing of Error Correcting Codes

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 process of recovering the original information from corrupted data is called decoding. Given the limitations imposed by the amount of redundancy used by the error correcting code, an ideal decoder should efficiently recover from as many errors as information-theoretically possible. In this thesis, we consider two relaxations of the usual decoding procedure: list decoding and property testing.

A list decoding algorithm is allowed to output a small list of possibilities for the original information that could result in the given corrupted data. This relaxation allows for efficient correction of significantly more errors than what is possible through usual decoding procedure which is always constrained to output the transmitted information.

Property testing of error correcting codes entails "spot checking" corrupted data to quickly determine if the data is very corrupted or has few errors. Such spot checkers are closely related to the beautiful theory of Probabilistically Checkable Proofs.