Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity

Locally correctable codes (LCCs) are codes C : Σ k → Σ n which admit local algorithms that can correct any individual symbol of a corrupted codeword via a minuscule number of queries. One of the central problems in algorithmic coding theory is to construct O(1)-query LCC with minimal block length. Alas, state-of-the-art of such codes requires exponential block length to admit O(1)-query algorithms for local correction, despite much attention during the last two decades.

This lack of progress prompted the study of relaxed LCCs, which allow the correction algorithm to abort (but not err) on small fraction of the locations. This relaxation turned out to allow constant-query correction algorithms for codes with polynomial block length. Specifically, prior work showed that there exist O(1)-query relaxed LCCs that achieve nearly-quartic block length n = k 4+α , for an arbitrarily small constant α > 0.

We construct an O(1)-query relaxed LCC with nearlylinear block length n = k 1+α , for an arbitrarily small constant α > 0. This significantly narrows the gap between the lower bound which states that there are no O(1)-query relaxed LCCs with block length n = k 1+o(1) . In particular, this resolves an open problem raised by Gur, Ramnarayan, and Rothblum (ITCS 2018).

• Tom Gur is supported by the UKRI Future Leaders Fellowship MR/S031545/1.