Locally Decodable Codes

Over 60 years of research in coding theory, that started with the works of Shannon andHamming, have given us nearly optimal ways to add redundancy to messages, encoding bitstrings representing messages into longer bit strings called codewords, in a way that themessage can still be recovered even if a certain fraction of the codeword bits are corrupted.Classical error-correcting codes, however, do not work well when messages are modernmassive datasets, because their decoding time increases (at least) linearly with the length ofthe message. As a result in typical applications large datasets are first partitioned into smallblocks, each of which is then encoded separately. Such encoding allows efficient randomaccessretrieval of the data, but yields poor noise resilience.Locally decodable codes are codes intended to address this seeming conflict betweenefficient retrievability and reliability. They are codes that simultaneously provide efficientrandom-access retrieval and high noise resilience by allowing reliable reconstruction of anarbitrary data bit from looking at only a small number of randomly chosen codeword bits.Apart from the natural application to data transmission and storage such codes haveimportant applications in cryptography and computational complexity theory. This reviewintroduces and motivates locally decodable codes, and discusses the central results of thesubject.Locally Decodable Codes assumes basic familiarity with the properties of finite fields and isotherwise self-contained. It will benefit computer scientists, electrical engineers, andmathematicians with an interest in coding theory.