[Jump to code hierarchy]

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 a received 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 received word (assuming the received word is within some tolerated corruption rate \(\delta\)). Efficiency of the decoding is quantified by the code’s query complexity \(r\), and decoding 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]. This was first shown for linear LDCs [9]. A binary 2-query LDC with recovery probability at least \(1/2+\epsilon\) at corruption rate \(\delta\) satisfies \(n \geq 2^{ck-1}\) with \(c = 1-H(1/2+3\delta\epsilon/14)\) [7; Thm. 4]. Here, \(H\) is the binary entropy function. Weaker exponential lower bounds hold for adaptive queries and for alphabets of fixed size [7; Sec. 3.3 and Appx. B]. LDCs with \(r=1\) do not exist for \(k\) above a constant depending on \(\delta\) and \(\epsilon\) [1].

Decoding

LDCs admit decoders whose runtime scales polylogarithmically with \(n\).A 2-query LDC with recovery probability \(1/2+\epsilon\) can be decoded with one quantum query to the received word at recovery probability at least \(1/2+4\epsilon/7\) [7; Thm. 1].An LDC whose decoder outputs the XOR of its \(2r\) queried bits can be decoded with \(r\) quantum queries at the same recovery probability [7; Thm. 5].

Notes

See [10] and Ref. [11,12] for introductions to LDCs and LCCs.

Cousins

References

  1. [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 80 (2000) DOI

  2. [2]

    S. Arora and B. Barak, Computational Complexity (Cambridge University Press, 2009) DOI

  3. [3]

    S. Yekhanin, “Locally Decodable Codes”, Foundations and Trends® in Theoretical Computer Science 6, 139 (2012) DOI

  4. [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 537 (1999) DOI

  5. [5]

    S. Kopparty and S. Saraf, “Guest Column”, ACM SIGACT News 47, 46 (2016) DOI

  6. [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. [7]

    I. Kerenidis and R. de Wolf, “Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument”, (2002) arXiv:quant-ph/0208062

  8. [8]

    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 477 (2008) arXiv:0705.3806 DOI

  9. [9]

    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 175 DOI

  10. [10]

    Z. Dvir, Lecture notes on locally decodable codes (2016) URL

  11. [11]

    S. Gopi, “Locality in coding theory”, PhD thesis, Princeton University, 2018.

  12. [12]

    I. F. Blake, Essays on Coding Theory (Cambridge University Press, 2024) DOI

  13. [13]

    T. Kaufman and M. Viderman, “Locally Testable vs. Locally Decodable Codes”, Lecture Notes in Computer Science 670 (2010) DOI

  14. [14]

    J. Briët and R. de Wolf, “Locally Decodable Quantum Codes”, (2008) arXiv:0806.2101

  15. [15]

    B. Hemenway, R. Ostrovsky, and M. Wootters, “Local Correctability of Expander Codes”, (2015) arXiv:1304.8129

  16. [16]

    A. Bhattacharyya, S. Gopi, and A. Tal, “Lower bounds for 2-query LCCs over large alphabet”, (2017) arXiv:1611.06980

  17. [17]

    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 262 (2004) DOI

  18. [18]

    R. Henry, “Polynomial Batch Codes for Efficient IT-PIR”, Proceedings on Privacy Enhancing Technologies 2016, 202 (2016) DOI

  19. [19]

    H. Zhang, E. Yaakobi, and N. Silberstein, “Multiset Combinatorial Batch Codes”, (2017) arXiv:1701.02708

  20. [20]

    S. Yekhanin, Locally Decodable Codes and Private Information Retrieval Schemes (Springer Berlin Heidelberg, 2010) DOI

Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: ldc

Cite as:
“Locally decodable code (LDC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/ldc, arXiv:2606.11484
BibTeX:
@incollection{eczoo_ldc,
title={Locally decodable code (LDC)},
booktitle={The Error Correction Zoo},
year={2026},
editor={Albert, Victor V. and Faist, Philippe},
eprint={2606.11484},
doi={10.48550/arXiv.2606.11484},
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.), 2026. https://errorcorrectionzoo.org/c/ldc, arXiv:2606.11484

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/properties/block/distributed_storage/ldc.yml.