Noga Ron-Zewi: High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Locally-correctable codes (LCCs) and locally-testable codes (LTCs) are special families of error-correcting codes that admit extremely efficient, i.e., sub-linear time, algorithms for error correction and detection, respectively, while making a few queries to the received word. These codes were originally studied in complexity theory because of their close relationship to program checking and probabilistically checkable proofs (PCPs), but subsequently they were extensively studied for their own sake.

In this work, we construct the first locally-correctable codes and locally-testable codes with constant rate, constant relative distance, and sub-polynomial query complexity and running time. Specifically, we show that there exist binary LCCs and LTCs with block length n, constant rate (which can even be taken arbitrarily close to 1), constant relative distance, and query complexity and running time (sqrt(logn))$. Previously such codes were known to exist only with query complexity and running time ^{beta}$ (for constant $eta > 0$), and there were several, quite different, constructions known.

Along the way, we also construct LCCs and LTCs over large (but constant) size alphabets, with the same query complexity and running time (sqrt(logn))$, which additionally have the property of approaching the "Singleton bound", so they have almost the best-possible relationship between their rate and distance. This has the surprising consequence that asking for a large alphabet error-correcting code to further be an LCC or LTC does not require any sacrifice in terms of rate and distance! Such a result was previously not known for any sub-linear query complexity.

Time permitting we will also discuss further recent progress on LTCs.

Joint work with Swastik Kopparty, Or Meir and Shubhangi Saraf