A locally decodable code (LDC) $C \colon \{0,1\}^k \to \{0,1\}^n$ is an error-correcting code that allows one to recover any bit of the original message with good probability while only reading a small number of bits from a corrupted codeword. A relaxed locally decodable code (RLDC) is a weaker notion where the decoder is additionally allowed to abort and output a special symbol $\bot$ if it detects an error. For a large constant number of queries $q$, there is a large gap between the blocklength $n$ of the best $q$-query LDC and the best $q$-query RLDC. Existing constructions of RLDCs achieve polynomial length $n = k^{1 + O(1/q)}$, while the best-known $q$-LDCs only achieve subexponential length $n = 2^{k^{o(1)}}$. On the other hand, for $q = 2$, it is known that RLDCs and LDCs are equivalent. We thus ask the question: what is the smallest $q$ such that there exists a $q$-RLDC that is not a $q$-LDC? In this work, we show that any linear $3$-query RLDC is in fact a $3$-LDC, i.e., linear RLDCs and LDCs are equivalent at $3$ queries. More generally, we show for any constant $q$, there is a soundness error threshold $s(q)$ such that any linear $q$-RLDC with soundness error below this threshold must be a $q$-LDC. This implies that linear RLDCs cannot have "strong soundness" -- a stricter condition satisfied by linear LDCs that says the soundness error is proportional to the fraction of errors in the corrupted codeword -- unless they are simply LDCs. In addition, we give simple constructions of linear $15$-query RLDCs that are not $q$-LDCs for any constant $q$, showing that for $q = 15$, linear RLDCs and LDCs are not equivalent. We also prove nearly identical results for locally correctable codes and their corresponding relaxed counterpart.

翻译：局部可译码码（LDC）$C \\colon \\{0,1\\}^k \\to \\{0,1\\}^n$ 是一种纠错码，允许以高概率恢复原始消息的任意比特，同时仅从受损码字中读取少量比特。松弛局部可译码码（RLDC）是一种更弱的概念，其中解码器在检测到错误时还可选择中止并输出特殊符号$\\bot$。对于较大的常数查询次数$q$，最优$q$查询LDC与最优$q$查询RLDC的码长$n$之间存在显著差距。现有RLDC构造可实现多项式长度$n = k^{1 + O(1/q)}$，而已知最优$q$-LDC仅能达到次指数长度$n = 2^{k^{o(1)}}$。另一方面，对于$q = 2$，已知RLDC与LDC等价。因此我们提出疑问：存在不是$q$-LDC的$q$-RLDC的最小$q$值是多少？本工作中，我们证明任何线性$3$查询RLDC实际上都是$3$-LDC，即线性RLDC与LDC在$3$查询下等价。更一般地，我们证明对于任意常数$q$，存在一个可靠性误差阈值$s(q)$，使得任何可靠性误差低于该阈值的线性$q$-RLDC必须是$q$-LDC。这意味着线性RLDC无法具有“强可靠性”——这是线性LDC满足的更严格条件，要求可靠性误差与受损码字中的错误比例成正比——除非它们本身就是LDC。此外，我们给出了线性$15$查询RLDC的简单构造，这些构造对于任意常数$q$均不是$q$-LDC，表明在$q = 15$时线性RLDC与LDC不等价。我们还针对局部可校正码及其对应的松弛变体证明了几乎相同的结果。