Locally decodable code (LDC)

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

Block code

Children

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

Cousin

Locally testable code (LTC) — There are relations between LDCs and LTCs [7].

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 - STOC ’04 (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

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/tree/main/codes/classical/properties/ltc/ldc.yml.