ECCC-Report TR23-110https://eccc.weizmann.ac.il/report/2023/110Comments and Revisions published for TR23-110en-usSun, 26 May 2024 14:38:15 +0300
Revision 1
| Asymptotically-Good RLCCs with $(\log{n})^{2+o(1)}$ Queries |
Gil Cohen,
Tal Yankovitz
https://eccc.weizmann.ac.il/report/2023/110#revision1Recently, 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.Sun, 26 May 2024 14:38:15 +0300https://eccc.weizmann.ac.il/report/2023/110#revision1
Paper TR23-110
| Asymptotically-Good RLCCs with $(\log{n})^{2+o(1)}$ Queries |
Gil Cohen,
Tal Yankovitz
https://eccc.weizmann.ac.il/report/2023/110Recently, 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.Tue, 25 Jul 2023 15:35:44 +0300https://eccc.weizmann.ac.il/report/2023/110