Locally Decodable Codes (LDCs) are error-correcting codes $C:Σ^n\rightarrow Σ^m$ with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length $m$ that is super-polynomial in $n$, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson et al. showed how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting, and introduce their variants in the insertion and deletion (Insdel) error setting. Insdel LDCs were first studied by Ostrovsky and Paskin-Cherniavsky, and are further motivated by recent advances in DNA random access bio-technologies, in which the goal is to retrieve individual files from a DNA storage database. Our first result is an exponential lower bound on the length of Hamming RLDCs making 2 queries, over the binary alphabet. This answers a question explicitly raised by Gur and Lachish. Our result exhibits a "phase-transition"-type behavior on the codeword length for constant-query Hamming RLDCs. We further define two variants of RLDCs in the Insdel-error setting, a weak and a strong version. On the one hand, we construct weak Insdel RLDCs with with parameters matching those of the Hamming variants. On the other hand, we prove exponential lower bounds for strong Insdel RLDCs. These results demonstrate that, while these variants are equivalent in the Hamming setting, they are significantly different in the insdel setting. Our results also prove a strict separation between Hamming RLDCs and Insdel RLDCs.

We revisit computationally relaxed locally decodable codes (crLDCs) (Blocki et al., Trans. Inf. Theory ’21) and give two new constructions. Our first construction is a Hamming crLDC that is conceptually simpler than prior constructions, leveraging digital signature schemes and an appropriately chosen Hamming code. Our second construction is an extension of our Hamming crLDC to handle insertion-deletion (InsDel) errors, yielding an InsDel crLDC. This extension crucially relies on the noisy binary search techniques of Block et al. (FSTTCS ’20) to handle InsDel errors. Both crLDC constructions have binary codeword alphabets, are resilient to a constant fraction of Hamming and InsDel errors, respectively, and under suitable parameter choices have poly-logarithmic locality and encoding length linear in the message length and polynomial in the security parameter. These parameters compare favorably to prior constructions in the poly-logarithmic locality regime.

We construct locally decodable codes (LDCs) to correct insertion-deletion errors in the setting where the sender and receiver share a secret key or where the channel is resource-bounded. Our constructions rely on a so-called “Hamming-to-InsDel” compiler (Ostrovsky and Paskin-Cherniavsky, ITS ‘15 & Block et al., FSTTCS '20), which compiles any locally decodable Hamming code into a locally decodable code resilient to insertion-deletion (InsDel) errors. While the compilers were designed for the classical coding setting, we show that the compilers still work in a secret key or resource-bounded setting. Applying our results to the private key Hamming LDC of Ostrovsky, Pandey, and Sahai (ICALP '07), we obtain a private key InsDel LDC with constant rate and polylogarithmic locality. Applying our results to the construction of Blocki, Kulkarni, and Zhou (ITC '20), we obtain similar results for resource-bounded channels; i.e., a channel where computation is constrained by resources such as space or time.

Insdel errors occur in communication systems caused by the loss of positional information of the message. Since the work by Guruswami and Wang, there have been some further investigations on the list decoding of insertion codes, deletion codes and insdel codes. However, unlike classical Hamming metric or even rank-metric, there are still many unsolved problems on list decoding of insdel codes. The contributions of this paper mainly consist of two parts. Firstly, we analyze the list decodability of random insdel codes. We show that list decoding of random insdel codes surpasses the Singleton bound when there are more insertion errors than deletion errors and the alphabet size is sufficiently large. Furthermore, our results reveal the existence of an insdel code that can be list decoded against insdel errors beyond its minimum insdel distance while still having polynomial list size. This provides a more complete picture on the list decodability of insdel codes when both insertion and deletion errors happen. Secondly, we construct a family of explicit insdel codes with efficient list decoding algorithm. As a result, we derive a Zyablov-type bound for insdel errors. Recently, after our results appeared, Guruswami et al. provided a complete solution for another open problem on list decoding of insdel codes. In contrast to the problems we considered, they provided a region containing all possible insertion and deletion errors that are still list decodable by some q-ary insdel codes of non-zero rate. More specifically, for a fixed number of insertion and deletion errors, while our paper focuses on maximizing the rate of a code that is list decodable against that amount of insertion and deletion errors, Guruswami et al. focuses on finding out the existence of a code with asymptotically non-zero rate which is list decodable against this amount of insertion and deletion errors.