The Simons Institute announces an October 6, 2021 lecture by Irit Dinur with the result in the title. This is a wonderful breakthrough. I am glad to mention that I have altogether 170 combined years of friendships with the authors. Here is the lecture announcement:

## Breakthroughs — Locally Testable Codes with Constant Rate, Distance, and Locality

Oct 6, 2021 10:00 am – 11:00 am

Speaker:

Irit Dinur (Weizmann Institute of Science)

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.

In this talk, Irit Dinur will describe a construction of such codes based on a new object which she and her collaborators call Square Cayley Complex.

Joint work with Shai Evra, Ron Livne, Alex Lubotzky, and Shahar Mozes.

Thanks for sharing!

Maybe it is worth highlighting that the double Cayley graphs and expander codes constructed in their paper are exactly the balanced product codes introduced in December 2020, Breuckmann-Eberhardt, https://arxiv.org/pdf/2012.09271.pdf.

In Section IV.B.2 (page 14) we define the balanced product of graphs which yields the double Cayley graphs as special case. Moreover, in our main conjecture (page 19) we give the definition of the balanced product of two expander codes associated to the Cayley-graphs of PGL(2) which coincides with their construction of codes.

Our conjecture was about quantum LDCP codes and was recently proven by Panteleev-Kalachev, who also show the LTC conjecture making use of our construction.

Dear Jens, thanks for the comment!

Pingback: Good Codes papers are on the arXiv | Combinatorics and more