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.