Chair of the colloquium: Prof. Prahladh Harsha (TIFR, Mumbai)
Release of the lecture video on YouTube: December 20, 2021 at 18:00 hrs Indian time
Interactive session on Zoom: January 04, 2022 at 11:30 hrs Indian time
Title: Locally testable codes with constant rate, distance, and locality
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.
Joint work with Shai Evra, Ron Livne, Alex Lubotzky, and Shahar Mozes.