{"id":"arxiv/2603.03717","url":"https://arxiv.org/abs/2603.03717","tags":["cs.IT","cs.CC","math.CO"],"score":0,"title":"When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs","domain":"cs.IT","source":"arxiv","authors":["Kuan Cheng","Xin Li","Songtao Mao"],"reviews":0,"subject":"cs.IT","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-04","reactions":{}}