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

Cousin

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

Your contribution is welcome!

on github.com (edit & pull request)

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