Self-Correction, Distance Estimation and Local Testing of Codes

We construct linear codes of almost-linear length and linear distance that can be locally self-corrected on average from a constant number of queries:

1. Given oracle access to a word $w\in\Sigma^n$ that is at least $\varepsilon$-close to a codeword $c$, and an index $i\in [n]$ to correct, with high probability over $i$ and over the internal randomness, the local algorithm returns a list of possible corrections that contains $c_i$.

2. Given oracle access to any word $w\in\Sigma^n$ and an index $i\in [n]$ to correct, there is a low probability, over $i$ and over the internal randomness, that the local algorithm returns a symbol that is not $c_i$ for some $c$ that is $\varepsilon$-close to $w$.

This extends to the case where the correction is of $t=O(1)$ indices $i_1,...,i_t\in [n]$ rather than one.

The definition generalizes many problems that were introduced in the literature of local algorithms for codes, including: local testing in the low error regime, average-case local list-decoding, and distance estimation. To the best of our knowledge, no previous construction for these problems obtained both nearly-optimal distance and length, and constant number of queries.

For the construction, we devise a new combinatorial operation for reducing the number of queries of self-correctable codes. The operation relies on ideas, techniques and constructions from PCP, but requires further ides.

Joint work with Michal Moshkovitz.