Constant Query Local Decoding Against Deletions Is Impossible
1Meghal Gupta (UC Berkeley)
https://simons.berkeley.edu/talks/meghal-gupta-uc-berkeley-2024-04-09
Advances in the Theory of Error-Correcting Codes
Locally decodable codes (LDC's) are error-correcting codes that allow recovery of individual message indices by accessing only a constant number of codeword indices. For substitution errors, it is clear that LDC's exist -- Hadamard codes are examples of 2-query LDC's, and research on this front has focused on finding the optimal encoding length for LDC's.
Ostrovsky and Paskin-Cherniavsky (ICITS 2015) introduced the notion of local decoding to the insertion and deletion setting. In this context, it is not clear whether constant query LDC's exist at all. Indeed, in contrast to the classical setting, Block et al. conjecture that they do not exist. Blocki et al. (FOCS 2021) make progress towards this conjecture, proving that any potential code must have at least exponential encoding length.
In this talk, we’ll show that constant query LDC's do not exist in the insertion/deletion (or even deletion-only) setting. Using a reduction shown by Blocki et al., this also implies that constant query locally correctable codes do not exist in this setting.