Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes

A locally decodable code (LDC) C ∶ 0,1k → 0,1n 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 ⊥ 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-known q-query LDC and the best-known q-query RLDC. Existing constructions of RLDCs achieve polynomial length n = k1 + O(1/q), while the best-known q-LDCs only achieve subexponential length n = 2ko(1). On the other hand, for q = 2, RLDCs and LDCs are equivalent as shown by Block, Blocki, Cheng, Grigorescu, Li, Zheng, and Zhu (CCC 2023). 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.