Shai Evra

Hebrew University of Jerusalem


Locally testable codes with constant rate, constant distance, and constant locality.


Combinatorics Seminar


20th September 2022, 11:00 am – 12:00 pm
Fry Building, G.07


A locally testable code (LTC) is an error correcting code that has a property tester, which reads q bits (q being the locality parameter of the tester) that are randomly chosen, and rejects words with probability proportional to their distance from the code. An outstanding open question has been whether there exist LTCs with constant rate, constant distance, and constant locality. In this talk I will describe a new construction of LTCs which gives an affirmative answer to this question.

This is based on a joint work with Irit Dinur, Ron Livne, Alex Lubotzky and Shahar Mozes.






Comments are closed.
css.php