Irit Dinur, Tali Kaufman, Noga Ron-Zewi

A local tester for an error-correcting code is a probabilistic procedure that queries a small subset of coordinates, accepts codewords with probability one, and rejects non-codewords with probability proportional to their distance from the code. The local tester is {\em robust} if for non-codewords it satisfies the stronger property that ... more >>>

Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes

A locally testable code (LTC) is an error correcting code that has a property-tester. The tester reads $q$ bits that are randomly chosen, and rejects words with probability proportional to their distance from the code. The parameter $q$ is called the locality of the tester.

LTCs were initially studied as ... more >>>