Revised: July 31, 2020
Published: December 30, 2020
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.
- 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)}))$.
- 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.