English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Locally Decodable Codes (LDCs) are error-correcting codes for whichindividual message symbols can be quickly recovered despite errors in thecodeword. LDCs for Hamming errors have been studied extensively in the past fewdecades, where a major goal is to understand the amount of redundancy that isnecessary and sufficient to decode from large amounts of error, with smallquery complexity.  In this work, we study LDCs for insertion and deletion errors, called InsdelLDCs. Their study was initiated by Ostrovsky and Paskin-Cherniavsky(Information Theoretic Security, 2015), who gave a reduction from Hamming LDCsto Insdel LDCs with a small blowup in the code parameters. On the other hand,the only known lower bounds for Insdel LDCs come from those for Hamming LDCs,thus there is no separation between them. Here we prove new, strong lowerbounds for the existence of Insdel LDCs. In particular, we show that $2$-querylinear Insdel LDCs do not exist, and give an exponential lower bound for thelength of all $q$-query Insdel LDCs with constant $q$. For $q \ge 3$ our boundsare exponential in the existing lower bounds for Hamming LDCs. Furthermore, ourexponential lower bounds continue to hold for adaptive decoders, and even inprivate-key settings where the encoder and decoder share secret randomness.This exhibits a strict separation between Hamming LDCs and Insdel LDCs.  Our strong lower bounds also hold for the related notion of Insdel LCCs(except in the private-key setting), due to an analogue to the Insdel notionsof a reduction from Hamming LCCs to LDCs.  Our techniques are based on a delicate design and analysis of harddistributions of insertion and deletion errors, which depart significantly fromtypical techniques used in analyzing Hamming LDCs.

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