[Jump to code hierarchy]

Locally correctable code (LCC)

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 LCC is a block code for which one can recover any coordinate of a codeword from at most \(r\) coordinates of the received word (assuming the received word is within some tolerated corruption rate \(\delta\)).

Modified versions of local correctability include relaxed local correctability [1].

Protection

Three-query LCCs have to have length that is superpolynomial in the message length [2].

Notes

See [3] and Ref. [4] for an introduction to LDCs and LCCs.See a popular summary of the result about three-query LCCs in Quanta Magazine.

Cousins

  • Locally decodable code (LDC)— Any family of LCCs can be converted to a family of LDCs whose rate differs by a constant [5]; see [4; Sec. 2.4.1].
  • Locally testable code (LTC)— There are relations between LDCs and LTCs [6].
  • Quantum locally recoverable code (QLRC)— A quantum code cannot admit two disjoint local recovery sets for the same qudit unless that qudit is fixed, ruling out a natural quantum analogue of LCCs [7; Thm. 74].
  • Analog code— LCCs can also be defined over the real or complex numbers, and there are no complex 2-query LCCs [8].

Member of code lists

Primary Hierarchy

Classical Domain
Error-correcting code (ECC)
Block code
Distributed-storage codeECC
Code with locality
Locally recoverable code (LRC)
Parents
Locally recoverable code (LRC)
LRCs recover a coordinate from a small number of other coordinates of an uncorrupted codeword, while LCCs allow recovery from a corrupted received word within the decoding radius. Since an uncorrupted codeword is a special case of a received word, any LCC is also an LRC.
Locally correctable code (LCC)
Children
\(q\)-ary linear LCCGRM

References

  1. [1]

    T. Gur, G. Ramnarayan, and R. Rothblum, Theory of Computing 16, 1 (2020) DOI

  2. [2]

    P. K. Kothari and P. Manohar, “An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes”, (2023) arXiv:2311.00558

  3. [3]

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

  4. [4]

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

  5. [5]

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

  6. [6]

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

  7. [7]

    L. Golowich and V. Guruswami, “Quantum Locally Recoverable Codes”, (2023) arXiv:2311.08653

  8. [8]

    B. Barak, Z. Dvir, A. Wigderson, and A. Yehudayoff, “Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes”, (2011) arXiv:1009.4375

Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: lcc

Cite as:
“Locally correctable code (LCC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/lcc, arXiv:2606.11484
BibTeX:
@incollection{eczoo_lcc,
title={Locally correctable code (LCC)},
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/lcc}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/lcc

Cite as:

“Locally correctable code (LCC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/lcc, arXiv:2606.11484

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