Foundations and Trends® in Theoretical Computer Science > Vol 6 > Issue 3

Locally Decodable Codes

By Sergey Yekhanin, Microsoft Research Silicon Valley, USA, yekhanin@microsoft.com

 
Suggested Citation
Sergey Yekhanin (2012), "Locally Decodable Codes", Foundations and TrendsĀ® in Theoretical Computer Science: Vol. 6: No. 3, pp 139-255. http://dx.doi.org/10.1561/0400000030

Publication Date: 16 Oct 2012
© 2012 S. Yekhanin
 
Subjects
Randomness in computation
 

Free Preview:

Download extract

Share

Download article
In this article:
1 Introduction 
2 Preliminaries 
3 Multiplicity Codes 
4 Matching Vector Codes 
5 Matching Vectors 
6 Lower Bounds 
7 Applications 
8 Future Directions 
Acknowledgments 
References 

Abstract

Locally decodable codes are a class of "error-correcting codes." Error-correcting codes help to ensure reliability when transmitting information over noisy channels. They allow a sender of a message to add redundancy to messages, encoding bit strings representing messages into longer bit strings called codewords, in a way that the message 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 one is working with massive messages, because their decoding time increases (at least) linearly with the length of the message. As a result in typical applications the message is first partitioned into small blocks, each of which is then encoded separately. Such encoding allows efficient random-access retrieval of the message, but yields poor noise resilience.

Locally decodable codes are codes intended to address this seeming conflict between efficient retrievability and reliability. They are codes that simultaneously provide efficient random-access retrieval and high noise resilience by allowing reliable reconstruction of an arbitrary bit of the message from looking at only a small number of randomly chosen codeword bits. This review introduces and motivates locally decodable codes, and discusses the central results of the subject. In particular, local decodability comes at the price of certain loss in terms of code efficiency, and this review describes the currently known limits on the efficiency that is achievable.

DOI:10.1561/0400000030
ISBN: 978-1-60198-544-6
124 pp. $85.00
Buy book (pb)
 
ISBN: 978-1-60198-545-3
124 pp. $110.00
Buy E-book (.pdf)
Table of contents:
1: Introduction
2: Preliminaries
3: Multiplicity Codes
4: Matching Vector Codes
5: Matching Vectors
6: Lower Bounds
7: Applications
8: Future Directions
Acknowledgements
References

Locally Decodable Codes

Over 60 years of research in coding theory, that started with the works of Shannon and Hamming, have given us nearly optimal ways to add redundancy to messages, encoding bit strings representing messages into longer bit strings called codewords, in a way that the message 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 modern massive datasets, because their decoding time increases (at least) linearly with the length of the message. As a result in typical applications large datasets are first partitioned into small blocks, each of which is then encoded separately. Such encoding allows efficient random-access retrieval of the data, but yields poor noise resilience. Locally decodable codes are codes intended to address this seeming conflict between efficient retrievability and reliability. They are codes that simultaneously provide efficient random-access retrieval and high noise resilience by allowing reliable reconstruction of an arbitrary 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 have important applications in cryptography and computational complexity theory. This book introduces and motivates locally decodable codes, and discusses the central results of the subject. Locally Decodable Codes assumes basic familiarity with the properties of finite fields and is otherwise self-contained. It will benefit computer scientists, electrical engineers, and mathematicians with an interest in coding theory.

 
TCS-030