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].
Notes
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 [3]; see [2; Sec. 2.4.1].
- Locally testable code (LTC) — There are relations between LDCs and LTCs [4].
- Quantum locally recoverable code (QLRC) — There is not a natural quantum version of LCCs [5; Thm. 9].
References
- [1]
- T. Gur, G. Ramnarayan, and R. Rothblum, Theory of Computing 16, 1 (2020) DOI
- [2]
- Gopi, Sivakanth. Locality in coding theory. Diss. Princeton University, 2018.
- [3]
- A. Bhattacharyya, S. Gopi, and A. Tal, “Lower bounds for 2-query LCCs over large alphabet”, (2017) arXiv:1611.06980
- [4]
- T. Kaufman and M. Viderman, “Locally Testable vs. Locally Decodable Codes”, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 670 (2010) DOI
- [5]
- L. Golowich and V. Guruswami, “Quantum Locally Recoverable Codes”, (2023) arXiv:2311.08653
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