## 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

## Abstract:

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.