Revised: July 31, 2020
Published: December 30, 2020
Abstract: [Plain Text Version]
Locally decodable codes (\LDCs) and locally correctable codes (\LCCs) 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 \LDCs, 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) \LDCs 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 \LCCs 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) \LCCs, 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) \LCCs 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.