2026-08-14T17:24:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8315 2024-03-06T10:42:05Z ddc:004 open_access

Relaxed Locally Correctable Codes Gur, Tom Ramnarayan, Govind Rothblum, Ron D. Keywords and phrases Coding Theory Locally Correctable Codes Probabilistically Checkable Proofs 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 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 almost-linear blocklength, which is sub-exponentially better than what is known for (full-fledged) LDCs in the constant-query regime. 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 a corruption. We give two 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 blocklength whose corrector only reads a constant number of bits of the codeword. This is a sub-exponential improvement over the best constant query (full-fledged) LCCs that are known. 2. Constant Rate: A relaxed LCC with constant rate (i.e., linear blocklength) with quasi-polylogarithmic query complexity. This is a nearly sub-exponential improvement over the query complexity of a recent (full-fledged) constant-rate LCC of Kopparty et al. (STOC, 2016). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tom Gur and Govind Ramnarayan and Ron D. Rothblum 2018 Is Part Of LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2018.27 urn:nbn:de:0030-drops-83154 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.27 eng https://creativecommons.org/licenses/by/3.0/legalcode