Asymptotically-Good RLCCs with $(\log{n})^{2+o(1)}$ Queries

by Gil Cohen and Tal Yankovitz

Oded's comments

(Glossary: LDC/LCC = locally decodable/correctable code, LTC = locally testable code.)

I did notice the work of Kumar and Mon, but chose not to recommend it because I did not like the write-up. So I am happy to recommend the present work, which provides a very clear presentation.

The current work reduces the construction of relaxed LDCs (and LCCs) to the construction of a weak form of locally testable codes (LTCs), which are (only) local testability in the vicinity of the code (as defined in Section 2.3.6 of my survey on short locally testable codes and proofs). Using this notion (which is satisfied by expander codes) rather than the overly strong notion of LTCs (see Section 2.3.1 versus Section 2.1 in my survey) is the key to the improved complexity of the current reduction. It also allows for a simpler presentation, which is provided in the current work.

I must admit that I never saw relaxed LDCs/LCCs as closely related to LTCs, and so I'm not too sympathetic to Kumar and Mon's claim thay they cement the relation between the two notions. What they showed was a very appealing reduction, which was overlooked by all prior researchers. The existence of a reduction (or even stronger relations) between notions does not cement them (cf., IP=PSPACE).

Warning (wrt the overview - Sec 2.2 in the new work): For block-length $n$, letting $m=O(\log n)$, the main construction works with binary codes of $1-(1/m)$ rate, which have only $\Omega(1/m)$ relative distance (see Sec 2.2.1-2.2.2). To improve the distance, it suffices to use a code of constant relative distance (and constant rate) at the highest level (see Sec 2.2.3). At the other levels, one keeps using the foregoing codes. The rate and distance are then dominated by the highest level.

The original 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^{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.

See ECCC TR23-110.


Back to list of Oded's choices.