Locally decodable code (LDC)[1] 


Recall that a block code encodes a length-\(k\) message into a length-\(n\) codeword, which is then sent through a noise channel to yield an error word. Informally, an LDC is a block code for which one can recover any coordinate of the message from at most \(r\) coordinates of the error word (assuming the error word is within some tolerated corruption rate \(\delta\)). Efficiency of the correction is quantified by the code's query complexity \(r\), and correction is performed by sampling subsets of \(r\) bits.

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

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


Families of LDCs with query complexity \(r=2\) need \(n\) to scale exponentially with \(k\) [7,8].


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


See notes by Z. Dvir and Ref. [9] for an introduction to LDCs and LCCs.





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
S. Arora and B. Barak, Computational Complexity (Cambridge University Press, 2009) DOI
S. Yekhanin, “Locally Decodable Codes”, Foundations and Trends® in Theoretical Computer Science 6, 139 (2012) DOI
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
S. Kopparty and S. Saraf, “Guest Column”, ACM SIGACT News 47, 46 (2016) DOI
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
I. Kerenidis and R. de Wolf, “Exponential lower bound for 2-query locally decodable codes via a quantum argument”, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (2003) DOI
O. Goldreich et al., “Lower bounds for linear locally decodable codes and private information retrieval”, Proceedings 17th IEEE Annual Conference on Computational Complexity DOI
Gopi, Sivakanth. Locality in coding theory. Diss. Princeton University, 2018.
T. Kaufman and M. Viderman, “Locally Testable vs. Locally Decodable Codes”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 670 (2010) DOI
B. Hemenway, R. Ostrovsky, and M. Wootters, “Local Correctability of Expander Codes”, (2015) arXiv:1304.8129
A. Bhattacharyya, S. Gopi, and A. Tal, “Lower bounds for 2-query LCCs over large alphabet”, (2017) arXiv:1611.06980
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
@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:

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/block/distributed_storage/ldc.yml.