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.
