Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Relaxed locally correctable codes:
TR20-142 | 15th September 2020
Vahid Reza Asadi, Igor Shinkar

Relaxed Locally Correctable Codes with Improved Parameters

Locally decodable codes (LDCs) are error-correcting codes $C : \Sigma^k \to \Sigma^n$ that admit a local decoding algorithm that recovers each individual bit of the message by querying only a few bits from a noisy codeword. An important question in this line of research is to understand the optimal trade-off ... more >>>

TR22-045 | 4th April 2022
Gil Cohen, Tal Yankovitz

Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring

Revisions: 1

In their highly influential paper, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004) introduced the notion of a relaxed locally decodable code (RLDC). Similarly to a locally decodable code (Katz-Trevisan; STOC 2000), the former admits access to any desired message symbol with only a few queries to a possibly corrupted ... more >>>

ISSN 1433-8092 | Imprint