Computer Science/Discrete Mathematics Seminar I
Locally testable codes with constant rate, distance, and locality, Part I
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.
Joint work with Shai Evra, Ron Livne, Alex Lubotzky, and Shahar Mozes.