I have been waiting for a couple of months to recommend this stunning result, which does not really need my recommendation. (I was present at an informal presentation of it, at Weizmann.)
Still, ever since Irit Dinur's seminal proof of the PCP Theorem (see ECCC TR05-046), which provided as a ``by product'' a LTC of 1/polylog rate, the question resolved by the current paper was on the table. I would not say that this question was on the table before, since I think that even the 1/polylog rate was not seen on the horizon. Prior to Irit's work, we were still making slow progress at much smaller rates (see , e.g., BGHSV).
In any case, inspired by prior studies of High-Dim Expanders, but actually stepping away from them, the current work provides a LTC of constant rate, where here and above I refer to the regime of constant number of queries (as opposed to prior work that achieved a quasi-polylogarithmic number of queries (see ECCC TR15-110)) and take constant relative distance for granted.
Needless to say, the current work challenges the two-regimes perspective (i.e., the constant query regime vs the constant rate regime) as well as the possibility that there is a trade-off between the level of locality (i.e., number of queries) and the rate of the code (or its length as opposed to ints information contents).
A locally testable code (LTC) is an error-correcting code together with a property tester. The tester reads a few random bits in the received word and decides if the word is in the code.
LTCs were initially studied as essential components of PCPs, and since then the topic has evolved on its own. High rate LTCs could be useful in practice: before attempting to decode a received word, one can save time by first quickly testing if it is close to the code.
An outstanding open question has been whether there exist LTCs that are "good" in the coding theory sense of having both constant relative distance and rate, and at the same time testable with a constant number of queries.
[This work provides] a construction of such codes based on a new object, called Square Cayley Complex.
Irit Dinur will be presenting this work on October 6 at 10-11AM PDT as part of the Simons Institute Fall 2021 Breakthroughs Series; participation requires registration via a form available HERE.