Recently, Kumar and Mon reached a significant milestone by constructing asymptotically good relaxed locally correctable codes (RLCCs) with poly-logarithmic query complexity. Specifically, they constructed $n$-bit RLCCs with $O(\log^{69}n)$ queries. This significant advancement relies on a clever reduction to locally testable codes (LTCs), capitalizing on recent breakthrough works in LTCs.

With regards to lower bounds, Gur and Lachish (SICOMP 2021) proved that any asymptotically-good RLCC must make at least $\widetilde{\Omega}(\sqrt{\log n})$ queries. Hence emerges the intriguing question regarding the identity of the least value $\frac1{2} \le e \le 69$ for which asymptotically-good RLCCs with query complexity $(\log n)^{e+o(1)}$ exist.

In this work, we make substantial progress in narrowing the gap by devising asymptotically-good RLCCs with a query complexity of $(\log n)^{2+o(1)}$. The key insight driving our work lies in recognizing that the strong guarantee of local testability overshoots the requirements for the Kumar-Mon reduction. Consequently, we can replace the LTCs by "vanilla" expander codes which indeed have the necessary property: local testability in the vicinity of the code.

We are grateful to Marcel Dall’Agnol and Pedro Paredes for identifying an inaccuracy in our original proof, which has been corrected in this revision. Additionally, this revision includes minor improvements to the text based on suggestions from anonymous reviewers.

Recently, Kumar and Mon reached a significant milestone by constructing asymptotically good relaxed locally correctable codes (RLCCs) with poly-logarithmic query complexity. Specifically, they constructed $n$-bit RLCCs with $O(\log^{69}n)$ queries. This significant advancement relies on a clever reduction to locally testable codes (LTCs), capitalizing on recent breakthrough works in LTCs.

With regards to lower bounds, Gur and Lachish (SICOMP 2021) proved that any asymptotically-good RLCC must make at least $\widetilde{\Omega}(\sqrt{\log n})$ queries. Hence emerges the intriguing question regarding the identity of the least value $\frac1{2} \le e \le 69$ for which asymptotically-good RLCCs with query complexity $(\log n)^{e+o(1)}$ exist.

In this work, we make substantial progress in narrowing the gap by devising asymptotically-good RLCCs with a query complexity of $(\log n)^{2+o(1)}$. The key insight driving our work lies in recognizing that the strong guarantee of local testability overshoots the requirements for the Kumar-Mon reduction. Consequently, we can replace the LTCs by "vanilla" expander codes which indeed have the necessary property: local testability in the vicinity of the code.