Low-Query Locally Testable Codes

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 are usually motivated because of their connection to probabilistically checkable proofs (PCPs).

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. In fact, 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 word. 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-query LTCs (with a huge alphabet), and that the DELLM construction can be explained by means of cosystolic expansion (of sheaves). 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.

I will survey the above works and then explain some of the key ideas of my work with Kaufman, namely, the use of sheaves (a.k.a. local systems) on cell complexes to construct codes with a 2-query tester, and the use of a novel (almost-)local criterion to establish their desired properties.