Locality in Coding Theory

Madhu Sudan (MSR)

An error-correcting code is said to be L-locally testable if given any word it can be determined whether it is close to a codeword or not by sampling only L coordinates of the word. A code (or more precisely an encoding scheme) is said to be L-locally decodable if given a received word that is close to some codeword, any single coordinate of the message being encoded can be computed by sampling only L-coordinates of the received word. When L is much smaller than N, the block length of the code, locally testable and correctible codes offer reliability associated with N-long codewords while producing decoding delays of only L-long codewords.

In this talk we will describe some of the motivations that led to the study of local codes in theoretical computer science and then describe some basic constructions and mention some of the state of the art results (due to Kopparty, Meir, Ron-Zewi and Saraf) that show codes of sub-polynomial locality (L = N^{o(1)}) close to the Singleton bound.