Irit Dinur "Locally testable codes via expanders"
Irit Dinur from Weizmann institute of science will give the talk "Locally testable codes via expanders" on the labs' Big Seminar.
Password: first 6 decimal places of $\pi$ after the decimal point
You can also write to Alexander Polyanskii (alexander.polyanskii@yandex.ru) or to Maksim Zhukovskii (zhukmax@gmail.com) if you want to be added to mailing list.
Abstract:
A locally testable code (LTC) is an error-correcting code that admits a very efficient membership test. The tester reads a constant number of (randomly - but not necessarily uniformly - chosen) bits from a given word and rejects words with probability proportional to their distance from the code.
LTCs were initially studied as important 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, I will describe a construction of such codes based on a new object called a left-right Cayley complex, which is a graph with squares. We will see how the expansion of this graph plays a key role.
Joint work with Shai Evra, Ron Livne, Alex Lubotzky, and Shahar Mozes.
SlidesWatch the video:
Everyone is invited to attend. The language of the lecture is English. The event is aimed at master and graduate students, as well as researchers in the field of combinatorics.