I am naturally very interested in this paper, although it does fall short of separating LDCs from RLDCs. While is constructs a $q$-query RLDC that encodes a message of length $k$ using a codeword of block length $O(k^{1+O(1/{q}}))$, the LDC lower bound asserts block length $\Omega(k^{1+(2/(q-2)}))$, for any even $q\geq4$.
Adding to the account in the abstract, I would mention that a recent lower bound by Gur and Lachish that asserts that $q$-query RLDC that encodes a message of length $k$ must use codewords of block length $n = \Omega(k^{1+1/\Omega(q^2)})$.
Correction: All foregoing bounds refer to non-adaptive algorithms. This makes the upper bounds stronger, but the lower bounds weaker (although $q$ adaptive queries can be emulated by $2^q$ non-adaptive queries). This gap is closed in a recent work.
Locally decodable codes (LDCs) are error-correcting codes $C : \Sigma^k \to \Sigma^n$ that admit a local decoding algorithm that recovers each individual bit of the message by querying only a few bits from a noisy codeword. An important question in this line of research is to understand the optimal trade-off between the query complexity of LDCs and their block length. Despite importance of these objects, the best known constructions of constant query LDCs have super-polynomial length, and there is a significant gap between the best constructions and the known lower bounds in terms of the block length.
For many applications it suffices to consider the weaker notion of relaxed LDCs (RLDCs), which allows the local decoding algorithm to abort if by querying a few bits it detects that the input is not a codeword. This relaxation turned out to allow decoding algorithms with constant query complexity for codes with almost linear length. Specifically, [Ben+06] constructed an $O(q)$-query RLDC that encodes a message of length $k$ using a codeword of block length $n = O(k^{1+1/\sqrt{q}})$.
In this work we improve the parameters of [Ben+06] by constructing an $O(q)$-query RLDC that encodes a message of length $k$ using a codeword of block length $O(k^{1+1/{q}})$. This construction matches (up to a multiplicative constant factor) the lower bounds of [KT00; Woo07] for constant query LDCs, thus making progress toward understanding the gap between LDCs and RLDCs in the constant query regime.
In fact, our construction extends to the stronger notion of relaxed locally correctable codes (RLCCs), introduced in [GRR18], where given a noisy codeword the correcting algorithm either recovers each individual bit of the codeword by only reading a small part of the input, or aborts if the input is detected to be corrupt.
Available from ECCC TR20-142.