View PDF HTML (experimental)

Abstract:Locally decodable codes (LDCs) are error-correcting codes that allow recovery of any single message symbol by probing only a small number of positions from the (possibly corrupted) codeword. Relaxed locally decodable codes (RLDCs) further allow the decoder to output a special failure symbol $\bot$ on a corrupted codeword. While known constructions of RLDCs achieve much better parameters than standard LDCs, it is intriguing to understand the relationship between LDCs and RLDCs. On the one hand, separation results (i.e., the existence of $q$-query RLDCs that are not $q$-query LDCs) are known for $q=3$ (Gur, Minzer, Weissenberg, and Zheng, arXiv:2512.12960, 2025) and $q \geq 15$ (Grigorescu, Kumar, Manohar, and Mon, arXiv:2511.02633, 2025). On the other hand, prior work (Block, Blocki, Cheng, Grigorescu, Li, Zheng, and Zhu, CCC 2023) shows that any $2$-query RLDC also gives a $2$-query LDC, and (Grigorescu, Kumar, Manohar, and Mon, arXiv:2511.02633, 2025) shows that any \emph{linear} $3$-query RLDC is also a linear $3$-query LDC. Furthermore, Grigorescu, Kumar, Manohar, and Mon (arXiv:2511.02633, 2025) show that when the soundness error of a \emph{linear} $q$-query RLDC with perfect completeness is below some threshold $s(q)$, the code must also be a linear $q$-query LDC with comparable parameters.
In this work, we extend the main result of Grigorescu, Kumar, Manohar, and Mon (arXiv:2511.02633, 2025) by removing the linearity requirement in the nonadaptive setting. Specifically, we show that every nonadaptive $(q,\delta,1,s)$-RLDC over a finite alphabet $\Sigma$ with $s<|\Sigma|^{-q}$ yields a $q$-query LDC with comparable decoding radius and error. Our results also extend to the setting of locally correctable codes (LCCs) and relaxed locally correctable codes (RLCCs). From this, we also obtain lower bounds for nonadaptive RLDCs from known LDC lower bounds.

Submission history

From: Songtao Mao [view email]
[v1] Wed, 4 Mar 2026 04:40:08 UTC (32 KB)
[v2] Wed, 9 Sep 2026 14:16:48 UTC (25 KB)