Constant Query Local Decoding Against Deletions Is Impossible

Explore a lecture on the impossibility of constant query local decoding against deletions in error-correcting codes. Delve into the world of locally decodable codes (LDCs) and their limitations in the context of insertion and deletion errors. Learn about the contrast between substitution errors, where LDCs like Hadamard codes exist, and the challenges posed by deletion errors. Discover the groundbreaking research that proves the non-existence of constant query LDCs in deletion-only settings. Understand the implications of this finding on locally correctable codes and its significance in the field of error-correcting codes. Gain insights into the work of researchers like Ostrovsky, Paskin-Cherniavsky, and Blocki, and how their contributions have shaped our understanding of LDCs in various error contexts.

Constant Query Local Decoding Against Deletions Is Impossible