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

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.

Breakthroughs is a lecture series highlighting major new developments in theoretical computer science and is geared toward a scientific audience. 

If you require accommodation for communication, please contact our Access Coordinator at simonsevents@berkeley.edu with as much advance notice as possible.