Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions

Jeremiah Blocki, Kuan Cheng, Elena Grigorescu +3

Locally Decodable Codes (LDCs) are error-correcting codes for which individual message symbols can be quickly recovered despite errors in the codeword. LDCs for Hamming errors have…