When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs

Kuan Cheng, Xin Li, Songtao Mao

Locally decodable codes (LDCs) are error correction codes that allow recovery of any single message symbol by probing only a small number of positions from the (possibly corrupted)…