Volume 16 (2020) Article 18 pp. 1-68
Relaxed Locally Correctable Codes
by
Revised: July 31, 2020
Published: December 30, 2020
[PDF (634K)]    [PS (4296K)]    [PS.GZ (772K)]
[Source ZIP]
Keywords: codes, PCPs, locally correctable codes
ACM Classification: Theory of Computation: Error-correcting codes
AMS Classification: 68R01, 68R99

Abstract: [Plain Text Version]


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.