Locally-Decodable Codes

Error-correcting codes provide a means for encoding a message into a redundant codeword so that the original message can be recovered even if a fraction of the symbols comprising the codeword is corrupted. Examples of error-correcting codes abound, but most codes cannot provide local access to the underlying codeword. In particular, in most codes, to retrieve even a single bit of the encoded message, the entire codeword must be read and decoded. An error-correcting code is called locally-decodable if any bit of the underlying message can be recovered by reading only a small number of bits of the (corrupted) codeword. Locally-decodable codes have found numerous applications including worst-case to average case reductions, probabilistically checkable proofs and private information retrieval.

Locally-decodable codes have three parameters of interest. The query-complexity which measures the number of symbols that need to be read to recover a bit of the underlying message. The fraction of errors that the code can tolerate, and the length of the codewords. If we restrict our attention to a fixed error-rate, the problem becomes one of designing codes where the query complexity and the codeword length are simultaneously small.

In this talk, I will review known constructions of locally-decodable codes and show how cryptographic notions of privacy can be used to extend and improve upon the existing constructions.