Irit Dinur 'Locally testable codes with constant rate, distance, and locality' | Big Seminar

It is our pleasure to share the Big Seminar talk "Locally testable codes
with constant rate, distance, and locality" by Irit Dinur.

Abstract:

A locally testable code (LTC) is an error-correcting code that admits a very efficient membership test. The tester reads a constant number of (randomly - but not necessarily uniformly - chosen) bits from a given word and rejects words with probability proportional to their distance from the code.
LTCs were initially studied as important 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, I will describe a construction of such codes based on a new object called a left-right Cayley complex, which is a graph with squares. We will see how the expansion of this graph plays a key role.

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