# Locally decodable code (LDC)[1]

## Description

Block code for which one can efficiently correct a given string. Efficiency of the correction is quantified by the code's query complexity \(u\), and correction is performed by sampling subsets of \(u\) bits. Local decodability may only be possible up to some tolerated corruption rate \(\delta\).

LDCs have applications in computational complexity theory and cryptography [3–5][2; Sec. 17.4].

Modified versions of local decodability include relaxed local decodability [6].

## Decoding

LDCs admit local decoders, i.e., decoders whose runtime scales polylogarithmically with \(n\).

## Parent

## Children

- Hadamard code — Hadamard codes are locally decodable [3].
- Generalized RM (GRM) code — GRM codes are locally decodable [3].

## Cousins

- Locally testable code (LTC) — There are relations between LDCs and LTCs [7].
- Expander code — Expander codes are locally decodable provided that the inner code satisfies certain properties; there exist code families with rate approaching one [8].
- Multiplicity code — There exist multiplicity codes with rate arbitrarily close to one that are locally decodable from a constant error fraction [9].

## References

- [1]
- J. Katz and L. Trevisan, “On the efficiency of local decoding procedures for error-correcting codes”, Proceedings of the thirty-second annual ACM symposium on Theory of computing (2000) DOI
- [2]
- S. Arora and B. Barak, Computational Complexity (Cambridge University Press, 2009) DOI
- [3]
- S. Yekhanin, “Locally Decodable Codes”, Foundations and Trends® in Theoretical Computer Science 6, 139 (2011) DOI
- [4]
- M. Sudan, L. Trevisan, and S. Vadhan, “Pseudorandom generators without the XOR Lemma (extended abstract)”, Proceedings of the thirty-first annual ACM symposium on Theory of Computing (1999) DOI
- [5]
- S. Kopparty and S. Saraf, “Guest Column”, ACM SIGACT News 47, 46 (2016) DOI
- [6]
- E. Ben-Sasson et al., “Robust pcps of proximity, shorter pcps and applications to coding”, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (2004) DOI
- [7]
- T. Kaufman and M. Viderman, “Locally Testable vs. Locally Decodable Codes”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 670 (2010) DOI
- [8]
- B. Hemenway, R. Ostrovsky, and M. Wootters, “Local Correctability of Expander Codes”, (2015) arXiv:1304.8129
- [9]
- S. Kopparty, S. Saraf, and S. Yekhanin, “High-rate codes with sublinear-time decoding”, Journal of the ACM 61, 1 (2014) DOI

## Page edit log

- Victor V. Albert (2023-05-05) — most recent

## Cite as:

“Locally decodable code (LDC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/ldc

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/properties/ltc/ldc.yml.