A locally correctable code is an error-correcting code for which a randomized algorithm recovers any requested coordinate of a codeword by reading only a bounded number of coordinates of a corrupted word (Dvir 2016).

For a binary injective encoding , a locally correctable code has an algorithm that makes at most queries and, for every message , requested coordinate , and word satisfying , returns with probability at least . Here is the Hamming distance. Correction recovers a coordinate of the encoded codeword, rather than merely a coordinate of the original message.

Janzer and Manohar (2026) proved that a binary linear code with three-query local correction, fixed , and fixed must have

where is big-omega notation. Reed-Muller codes attain , where is big-O notation, so the dependence on is optimal up to constant factors in the exponent. The result is specific to binary linear codes and three queries. Janzer and Manohar (2026) credit GPT-6 Astra with completing key parts of their proof approach, which they subsequently simplified.

The definition also extends to codes over infinite fields. For every integer , put , where is the floor function. Dvir (2026) constructed, for every integer , a linear code over the real numbers of dimension and length

It corrects any requested coordinate with probability at least using at most queries when at most coordinates are corrupted. The decoder returns a linear combination of the queried coordinates. The same construction works over every field of characteristic zero. Dvir (2026) attributes the construction to ChatGPT Astra.

See also

Codeword, Error-Correcting Code, Hamming Distance, Linear Code, Reed-Muller Code

Explore with Wolfram|Alpha

References

Dvir, Z. "Constant Query LCCs Over the Reals." 9 Nov 2026. https://arxiv.org/abs/2611.13281v1.Dvir, Z. "Locally Correctable Codes." Lecture 8 in Linear Locally Decodable Codes. 2016. https://www.cs.princeton.edu/~zdvir/LDCnotes/LDC8.pdf.Janzer, O. and Manohar, P. "Reed-Muller Codes Are Optimal Binary Linear 3-Query LCCs." 2 Nov 2026. https://arxiv.org/abs/2611.03145v1.

Cite this as:

Weisstein, Eric W. "Locally Correctable Code." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LocallyCorrectableCode.html

Subject classifications