Title: Low-query locally testable error correcting codes


Abstract:
I will present and discuss the problem of constructing locally testable error correcting codes and its recent solution. No prior knowledge of error correcting codes will be assumed.
In more detail, everyday online communication relies on error correcting codes, which allow one to overcome errors in communication, namely, when every letter or bit transmitted has a small chance of being flipped. An error correcting code is called good if it can overcome a constant fraction of errors and introduces only a constant-percentage-increase in communication. The construction of good error correcting codes very often involves mathematics.
Locally testable codes (LTCs) are a special kind of error correcting codes where the receiver can correctly detect, with high probability, whether the received data was significantly corrected by reading just a few of its letters (chosen at random according to some distribution). This is useful because decoding very corrupted data may be time-consuming --- it is better to ask for retransmission in such a case. However, LTCs were originally motivated by computational complexity theory because of their connection to probabilistically checkable proofs. 
While good error correcting codes were well-known to exist almost since the topic was founded, the existence of good LTCs remained open for a long time. Rather, LTCs were even shown to be constrained, e.g., Ben-Sasson, Goldreich and Sudan showed that there are no good 2-query LTCs on a binary alphabet, where "2-query" means that one is allowed to read only 2 letters from the received data. Surprisingly, Dinur-Evra-Lubotzky-Livne-Mozes and Panteleev-Kalachev (independently) showed recently that good LTCs do exist. In a more recent work with Tali Kaufman, we showed that there are even good 2-querly LTCs (with a huge alphabet), and that the DELLM construction can be explained by means of cosystolic expansion. Finally, in a recent (still unpublished) work with Stav Lazarovich, we show that good 2-query LTCs exist for every alphabet of 3 or more letters, so the restriction proved by Ben-Sasson, Goldreich and Sudan is the only one.


Recording Link: https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=d858a6f8-472e-457e-828f-b30700571718