Live briefing
Everything about Locally decodable code
Type of error-correcting code
A locally decodable code (LDC) is an error-correcting code that allows a single bit of the original message to be decoded with high probability by only examining a small number of bits of a possibly corrupted codeword. This property could be useful, say, in a context where information is being transmitted over a noisy channel, and only a small subset of the data is required at a particular time and there is no need to decode the entire message at once. Locally decodable codes are not a subset of locally testable codes, though there is some overlap between the two. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: Locally decodable codeA 5-minute orientation
- Skim a recent paper: Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi GraphsInfluential work since 2022
- Pick up a classic book: Data Communications and NetworkingThe most-reprinted book on the subject
- Read the landmark paper: Towards 3-query locally decodable codes of subexponential lengthCited 156 times
- Go sideways: Folded Reed–Solomon codeA closely related topic
- Go sideways: Locally testable codeA closely related topic
đź“– Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Towards 3-query locally decodable codes of subexponential length
Locally Decodable Codes
Exponential lower bound for 2-query locally decodable codes via a quantum argument
Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
3-Query Locally Decodable Codes of Subexponential Length
Lower bounds for linear locally decodable codes and private information retrieval
Improved Constructions for Query-Efficient Locally Decodable Codes of Subexponential Length
Query-Efficient Locally Decodable Codes of Subexponential Length
🆕 Influential since 2022
đź“š Books worth reading
Data Communications and NetworkingBehrouz A. Forouzan, Catherine Ann Coombs · 2000
Information processing by neuronal populationsChristian Holscher, Matthias Munk · 2008
Locally decodable codes and private information retrieval schemesSergey Yekhanin · 2010
Real World HaskellBryan O'Sullivan, John Goerzen · 2008- 📕Locally Decodable CodesSergey Yekhanin · 2011
Coding the MatrixPhilip N. Klein · 2013
Intelligent Science and Intelligent Data EngineeringJian Yang · 2013
Introduction to computing systemsYale N. Patt, Sanjay J. Patel · 2003
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
đź”— Related topics
- Folded Reed–Solomon code In coding theory, folded Reed–Solomon codes are like Reed–Solomon codes, which are obtained by mapping m {\displaystyle m} Reed–Solomon codewords over…
- Locally testable code A locally testable code is a type of error-correcting code for which it can be determined if a string is a word in that code by looking at a small (frequently…
- List decoding In coding theory, list decoding is an alternative to unique decoding of error-correcting codes for large error rates. The notion was proposed by Elias…
- Decoding methods In coding theory, decoding is the process of translating received messages into codewords of a given code. There have been many common methods of mapping…
- Generalized minimum-distance decoding In coding theory, generalized minimum-distance (GMD) decoding provides an efficient algorithm for decoding concatenated codes, which is based on using…
- Hadamard code The Hadamard code is an error-correcting code named after the French mathematician Jacques Hadamard that is used for error detection and correction when…
- Binary symmetric channel A binary symmetric channel (or BSCp) is a common communications channel model used in coding theory and information theory. In this model, a transmitter…
- Guruswami–Sudan list decoding algorithm In coding theory, list decoding is an alternative to unique decoding of error-correcting codes in the presence of many errors. If a code has relative distance…