  Locally Decodable Codes (LDCs) are error-correcting codes
$C:\Sigma^n\rightarrow \Sigma^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.
