When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.03717
curl -X POST /api/v1/records/arxiv/2603.03717/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.03717/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'