Theory of Computing
-------------------
Title     : Relaxed Locally Correctable Codes
Authors   : Tom Gur, Govind Ramnarayan, and Ron Rothblum
Volume    : 16
Number    : 18
Pages     : 1-68
URL       : https://theoryofcomputing.org/articles/v016a018

Abstract
--------

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.

  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) LCCs, 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) 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.