COMPUTER SCIENCE AND DISCRETE MATHEMATICS SEMINAR | |

Topic: | Self-Correction, Distance Estimation and Local Testing of Codes |

Speaker: | Dana Moshkovitz |

Affiliation: | Massachusetts Institute of Technology |

Date: | Monday, November 29 |

Time/Room: | 3:15pm - 4:15pm/S-101 |

Video Link: | https://video.ias.edu/csdm/moshkovitz |

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.