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] for an introduction 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 [10].
Expander code — Expander codes are locally decodable provided that the inner code satisfies certain properties; there exist code families with rate approaching one [11].
Locally correctable code (LCC) — Any family of LCCs can be converted to a family of LDCs whose rate differs by a constant [12]; see [9; Sec. 2.4.1].

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 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]: 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
[8]: O. Goldreich et al., “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]: T. Kaufman and M. Viderman, “Locally Testable vs. Locally Decodable Codes”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 670 (2010) DOI
[11]: B. Hemenway, R. Ostrovsky, and M. Wootters, “Local Correctability of Expander Codes”, (2015) arXiv:1304.8129
[12]: A. Bhattacharyya, S. Gopi, and A. Tal, “Lower bounds for 2-query LCCs over large alphabet”, (2017) arXiv:1611.06980

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.