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 LCC is a block code for which one can recover any coordinate of a codeword from at most \(r\) coordinates of the error word (assuming the error 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 notes by Z. Dvir and Ref. [3] for an introduction to LDCs and LCCs.See popular summary of the result about three-query LCCs in Quanta Magazine.
Parent
- Locally recoverable code (LRC) — LRCs (LCCs) allow one to recover any coordinate of a codeword from at most \(r\) coordinates of a codeword (an error word within the decoding radius). Since a codeword is a trivial error word, any LCC is also an LRC.
Child
Cousins
- Locally decodable code (LDC) — Any family of LCCs can be converted to a family of LDCs whose rate differs by a constant [4]; see [3; Sec. 2.4.1].
- Locally testable code (LTC) — There are relations between LDCs and LTCs [5].
- Quantum locally recoverable code (QLRC) — There is not a natural quantum version of LCCs [6; Thm. 9].
- Sphere packing — LCCs can also be defined over the real or complex numbers, and there are no complex 2-query LCCs [7].
References
- [1]
- T. Gur, G. Ramnarayan, and R. Rothblum, Theory of Computing 16, 1 (2020) DOI
- [2]
- P. K. Kothari and P. Manohar, “An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes”, (2023) arXiv:2311.00558
- [3]
- Gopi, Sivakanth. Locality in coding theory. Diss. Princeton University, 2018.
- [4]
- A. Bhattacharyya, S. Gopi, and A. Tal, “Lower bounds for 2-query LCCs over large alphabet”, (2017) arXiv:1611.06980
- [5]
- T. Kaufman and M. Viderman, “Locally Testable vs. Locally Decodable Codes”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 670 (2010) DOI
- [6]
- L. Golowich and V. Guruswami, “Quantum Locally Recoverable Codes”, (2023) arXiv:2311.08653
- [7]
- 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
- Victor V. Albert (2023-03-27) — most recent
Cite as:
“Locally correctable code (LCC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/lcc