Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with PCPs of Proximity:
TR07-115 | 19th November 2007
Or Meir

Combinatorial Construction of Locally Testable Codes

An error correcting code is said to be 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 constant number of symbols of the string. Locally Testable Codes (LTCs) were first systematically studied by ... more >>>

TR14-025 | 25th February 2014
Oded Goldreich, Tom Gur, Ilan Komargodski

Strong Locally Testable Codes with Relaxed Local Decoders

Locally testable codes (LTCs) are error-correcting codes
that admit very efficient codeword tests. An LTC is said to
be strong if it has a proximity-oblivious tester;
that is, a tester that makes only a constant number of queries
and reject non-codewords with probability that depends solely
on their distance from ... more >>>

TR17-143 | 26th September 2017
Tom Gur, Govind Ramnarayan, Ron Rothblum

Relaxed Locally Correctable Codes

Revisions: 1

Locally decodable codes (LDCs) and locally correctable codes (LCCs) are error-correcting codes in which individual bits of the message and codeword, respectively, can be recovered by querying only few bits from a noisy codeword. These codes have found numerous applications both in theory and in practice.

A natural relaxation of ... more >>>

ISSN 1433-8092 | Imprint