Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Shai Evra:

TR21-151 | 8th November 2021
Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes

Locally Testable Codes with constant rate, distance, and locality

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

ISSN 1433-8092 | Imprint