To Cheer you up in difficult times 30: Irit Dinur, Shai Evra, Ron Livne, Alex Lubotzky, and Shahar Mozes Constructed Locally Testable Codes with Constant Rate, Distance, and Locality

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.