2026-07-25T11:48:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20404 2024-07-15T12:26:45Z ddc:004 open_access

Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries Cohen, Gil Yankovitz, Tal Relaxed locally decodable codes Relxaed locally correctable codes RLCC RLDC 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. Their construction relies on a clever reduction to locally testable codes (LTCs), capitalizing on recent breakthrough works in LTCs. As for lower bounds, Gur and Lachish (SICOMP 2021) proved that any asymptotically-good RLCC must make Ω̃(√{log n}) queries. Hence emerges the intriguing question regarding the identity of the least value 1/2 ≤ 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. In particular, we prove that we can replace the LTCs by "vanilla" expander codes which indeed have the necessary property: local testability in the code’s vicinity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gil Cohen and Tal Yankovitz 2024 Is Part Of LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2024.8 urn:nbn:de:0030-drops-204045 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.8 eng https://creativecommons.org/licenses/by/4.0/legalcode