Locality in Coding Theory

Madhu Sudan
Microsoft Research

A local algorithm for a given algorithmic task is one that runs in time much less than the length of the input and produces an implicit description of the output. Error-detection and Error-correction are classical algorithmic tasks associated with coding theory. Local algorithms for these tasks are well motivated concepts --- when the data being encoded is massive and one wishes to test for errors, or correct them without scanning the entire data. Codes that admit such local algorithms for error-detection are called locally testable codes (LTCs), and those that admit local algorithms for error-correction are called locally decodable codes (LDCs). In this talk, we will describe some of the basic LTCs and LDCs, and describe some new results that lead to LDCs and LTCs of high rate.

Based on joint work with Alan Guo and Swastik Kopparty.