I ended my review of the new-at-the-time almost-cubic lower bound of the length of 3-query LDC saying that it may be time to revisit the problem of constructing relaxed LDCs. This came after saying that a back-on-the-evelop calculation for the length of almost quadratic relaxed LDC yield a number of queries that exdeeds 10, to say the least. Hence, the current work that provides a 3-query relaxed LDC of almost quadradic length is remarkable as far as I am concerned, although it uses a constant size alphabet rather than a binary alphabet (since the aforementioned lower bound extends to constant-size alphabets).
In other words, the original motivation for introducing relaxed LDCs (rLDCs) was to bypass the performace of LDC. So any natural result that testifies to the advantage of the relaxation is great, and such evidence is provided by the current work. (Recall that all know constant-query LDCs are of super-polynomial length, whereas the lower-bounds on the length of $q$-query LDC have the form $k^{1+Omega(1/q)}$. Furthermore, the same asymptotic form (of the lower-bound) applies to rLDC, and this result is tight (see HERE).)
We construct $3$-query relaxed locally decodable codes (RLDCs) with constant alphabet size and length $\tilde{O}(k^2)$ for $k$-bit messages. Combined with the lower bound of $\tilde{\Omega}(k^3)$ of [Alrabiah, Guruswami, Kothari, Manohar, STOC 2023] on the length of locally decodable codes (LDCs) with the same parameters, we obtain a separation between RLDCs and LDCs, resolving an open problem of [Ben-Sasson, Goldreich, Harsha, Sudan and Vadhan, SICOMP 2006].
Our RLDC construction relies on two components. First, we give a new construction of probabilistically checkable proofs of proximity (PCPPs) with $3$ queries, quasi-linear size, constant alphabet size, perfect completeness, and small soundness error. This improves upon all previous PCPP constructions, which either had a much higher query complexity or soundness close to $1$. Second, we give a query-preserving transformation from PCPPs to RLDCs.
At the heart of our PCPP construction is a $2$-query decodable PCP (dPCP) with matching parameters, and our construction builds on the HDX-based PCP of [Bafna, Minzer, Vyas, Yun, STOC 2025] and on the efficient composition framework of [Moshkovitz, Raz, JACM 2010] and [Dinur, Harsha, SICOMP 2013]. More specifically, we first show how to use the HDX-based construction to get a dPCP with matching parameters but a large alphabet size, and then prove an appropriate composition theorem (and related transformations) to reduce the alphabet size in dPCPs.
See ECCC TR25-217.