Volume 16 (2020) Article 18 pp. 1-68

Relaxed Locally Correctable Codes

by Tom Gur, Govind Ramnarayan, and Ron Rothblum

Received: December 2, 2017
Revised: July 31, 2020
Published: December 30, 2020

$ \newcommand{\wt}{\tilde} \newcommand{\LCC}{\mathsf{LCC}} \newcommand{\LDC}{\mathsf{LDC}} $

Locally decodable codes ($\LDC$s) and locally correctable codes ($\LCC$s) are error-correcting codes in which individual bits of the message and codeword, respectively, can be recovered by querying only a few bits from a noisy codeword. These codes have found numerous applications both in theory and in practice.

A natural relaxation of $\LDC$s, introduced by Ben-Sasson et al. (SICOMP, 2006), allows the decoder to reject (i.e., refuse to answer) in case it detects that the codeword is corrupt. They call such a decoder a relaxed decoder and construct a constant-query relaxed $\LDC$ with nearly linear block length, whereas the state-of-the-art (full-fledged) $\LDC$s in the constant-query regime have superpolynomial block length.

We consider an analogous relaxation for local correction. Thus, a relaxed local corrector reads only few bits from a (possibly) corrupt codeword and either recovers the desired bit of the codeword, or rejects in case it detects corruption.

We give constructions of relaxed $\LCC$s in two regimes, where the first optimizes the query complexity and the second optimizes the rate.

1. Constant Query Complexity: A relaxed $\LCC$ with polynomial block length whose corrector only reads a constant number of bits of the codeword. In contrast, the best upper bound on the block length achieved by known $q$-query (full-fledged) $\LCC$s, for constant $q$, is $\exp(O(n^{1/(q-1)}))$.

2. Constant Rate: A relaxed $\LCC$ with constant rate (i.e., linear block length) with quasi-polylogarithmic query complexity (specifically, $\exp(O(\log\log n)^2)$). In contrast, the best known upper bound on the query complexity of constant-rate (full-fledged) $\LCC$s is $\exp(\wt{O}(\sqrt{\log n}))$ (Kopparty et al., STOC'16). Our construction, however, is based on a locally testable code constructed by Kopparty et al., which we show to allow for relaxed local correction with better parameters.

DOI: 10.4086/toc.2020.v016a018

© 2020 Tom Gur, Govind Ramnarayan, and Ron Rothblum
Licensed under a Creative Commons Attribution License (CC-BY)