Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOCALLY TESTABLE CODES:
Reports tagged with locally testable codes:
TR18-198 | 22nd November 2018
Irit Dinur, Tali Kaufman, Noga Ron-Zewi

From Local to Robust Testing via Agreement Testing

Revisions: 1

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 >>>




ISSN 1433-8092 | Imprint