Combinatorics Seminar - Spring '20

When: Sunday, April 11, 10am

Where: Schreiber 309

Speaker: Shai Evra, Hebrew University

Title: Locally Testable Codes with Constant Rate, Distance, and Locality


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.