Locally decodable code (LDC)

Locally decodable code (LDC)[1]

Description

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 [3–5][2; Sec. 17.4].

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

Rate

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

Decoding

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

Notes

See notes by Z. Dvir and Ref. [9,10] for introductions to LDCs and LCCs.

Parent

Block code

Child

\(q\)-ary linear LCC — Linear LCCs can be converted into LDCs with the same locality \(r\) [9; Sec. 2.4.1].

Cousins

Locally testable code (LTC) — There are relations between LDCs and LTCs [11].
Quantum locally recoverable code (QLRC) — There are quantum versions of LDCs, but they can be transformed into LDCs which can be decoded well on average [12].
Expander code — Expander codes are locally decodable provided that the inner code satisfies certain properties; there exist code families with rate approaching one [13].
Locally correctable code (LCC) — Any family of LCCs can be converted to a family of LDCs whose rate differs by a constant [14]; see [9; Sec. 2.4.1].
Batch code — Batch codes and LDCs are related [15,16][10; Ch. 10.3].
Private information retrieval (PIR) code — Any smooth LDC yields a PIR scheme [17]; see also Ref. [18].

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 (2012) 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, O. Goldreich, P. Harsha, M. Sudan, and S. Vadhan, “Robust pcps of proximity, shorter pcps and applications to coding”, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing 1 (2004) DOI
[7]: A. Ben-Aroya, O. Regev, and R. de Wolf, “A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs”, 2008 49th Annual IEEE Symposium on Foundations of Computer Science (2008) arXiv:0705.3806 DOI
[8]: O. Goldreich, H. Karloff, L. J. Schulman, and L. Trevisan, “Lower bounds for linear locally decodable codes and private information retrieval”, Proceedings 17th IEEE Annual Conference on Computational Complexity DOI
[9]: Gopi, Sivakanth. Locality in coding theory. Diss. Princeton University, 2018.
[10]: I. F. Blake, Essays on Coding Theory (Cambridge University Press, 2024) DOI
[11]: T. Kaufman and M. Viderman, “Locally Testable vs. Locally Decodable Codes”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 670 (2010) DOI
[12]: J. Briët and R. de Wolf, “Locally Decodable Quantum Codes”, (2008) arXiv:0806.2101
[13]: B. Hemenway, R. Ostrovsky, and M. Wootters, “Local Correctability of Expander Codes”, (2015) arXiv:1304.8129
[14]: A. Bhattacharyya, S. Gopi, and A. Tal, “Lower bounds for 2-query LCCs over large alphabet”, (2017) arXiv:1611.06980
[15]: Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai, “Batch codes and their applications”, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (2004) DOI
[16]: R. Henry, “Polynomial Batch Codes for Efficient IT-PIR”, Proceedings on Privacy Enhancing Technologies 2016, 202 (2016) DOI
[17]: H. Zhang, E. Yaakobi, and N. Silberstein, “Multiset Combinatorial Batch Codes”, (2017) arXiv:1701.02708
[18]: S. Yekhanin, Locally Decodable Codes and Private Information Retrieval Schemes (Springer Berlin Heidelberg, 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/edit/main/codes/classical/properties/block/distributed_storage/ldc.yml.