Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with LTC:
TR11-055 | 14th April 2011
Irit Dinur, Tali Kaufman

Dense locally testable codes cannot have constant rate and distance

A q-query locally testable code (LTC) is an error correcting code that can be tested by a randomized algorithm that reads at most q symbols from the given word.
An important question is whether there exist LTCs that have the ccc property: {c}onstant relative rate, {c}onstant relative distance, and that ... more >>>

ISSN 1433-8092 | Imprint