Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic

self-correcting algorithm that, with high probability, can correct any coordinate of the

codeword by looking at only a few other coordinates, even if a fraction $\delta$ of the

coordinates are corrupted. LCC's are a stronger form ...
more >>>

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf

We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry (AG) base-code of block-length $q$ to a lifted-code of block-length $q^m$, for arbitrary integer $m$. The construction generalizes the way degree-$d$, univariate polynomials evaluated over the $q$-element field (also known as Reed-Solomon codes) are "lifted" ... more >>>

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. 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 ... more >>>

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf

An error correcting code is said to be \emph{locally testable} if

there is a test that checks whether a given string is a codeword,

or rather far from the code, by reading only a small number of symbols

of the string. Locally testable codes (LTCs) are both interesting

in their ...
more >>>