Constant Query Local Decoding Against Deletions Is Impossible
summary
Proves that constant‑query locally decodable codes for insertions and deletions do not exist: a reduction of Blocki et al. plus an information‑theoretic bucketing argument shows one‑query and two‑query decoders fail under deletions (deletion‑only case already suffices) and hence constant‑query locally correctable codes also fail. Key ideas: adversary deletion patterns that equalize query outcome distributions, grouping queries into few indistinguishable buckets, and sharpening the prior exponential encoding length barrier. Result holds for constant alphabet and against oblivious deletions.
AI-written summary · about
chapters (12)
- 0:00Constant query LDCs intro
- 1:16What is a locally decodable code
- 4:48Insert vs deletion errors
- 6:34Main claim: no constant query LDCs
- 9:48Prior work background
- 13:06One and two query cases
- 18:08Adversary strategies for deletions
- 22:40Two query case and error distribution
- 29:52Exponential lower bounds
- 31:16Key idea beyond bounds
- 33:06Conclusions and open questions
- 38:23Q&A
related talks
46mCryptography with Certified Deletion
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics
21mQuantum Proofs of Deletion for Learning with Errors
34mPrivate Information Retrieval: Chasing Capacity with Algebraic Codes
01h 07mComputing on Encrypted Data via Secret Dual Codes
41mHigh-Rate Fair-Density Parity-Check Codes
01h 10mNon-Malleable Codes in the Split-State Model
01h 00mError-Correcting Codes That Enable Efficient SNARKs