Abstract
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 n)^69) 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 Ω~(logn) queries. Hence emerges the intriguing question regarding the identity of the least value ½ ≤ e ≤ 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.
Based on joint work with Gil Cohen.