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 [35][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

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

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: ldc

Cite as:
“Locally decodable code (LDC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/ldc
BibTeX:
@incollection{eczoo_ldc, title={Locally decodable code (LDC)}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/ldc} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/ldc

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.