Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RELAXED LOCALLY DECODABLE CODES:
Reports tagged with Relaxed locally decodable 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 >>>


TR23-067 | 7th May 2023
Guy Goldberg

Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error

Revisions: 2

Relaxed locally decodable codes (RLDCs) are error-correcting codes in which individual bits of the message can be recovered by querying only a few bits from a noisy codeword.
Unlike standard (non-relaxed) decoders, a relaxed one is allowed to output a ``rejection'' symbol, indicating that the decoding failed.
To prevent the ... more >>>


TR23-093 | 29th June 2023
Vinayak Kumar, Geoffrey Mon

Relaxed Local Correctability from Local Testing

Revisions: 1

We cement the intuitive connection between relaxed local correctability and local testing by presenting a concrete framework for building a relaxed locally correctable code from any family of linear locally testable codes with sufficiently high rate. When instantiated using the locally testable codes of Dinur et al. (STOC 2022), this ... more >>>


TR23-110 | 25th July 2023
Gil Cohen, Tal Yankovitz

Asymptotically-Good RLCCs with $(\log{n})^{2+o(1)}$ Queries

Revisions: 1

Recently, Kumar and Mon reached a significant milestone by constructing asymptotically good relaxed locally correctable codes (RLCCs) with poly-logarithmic query complexity. Specifically, they constructed $n$-bit RLCCs with $O(\log^{69}n)$ queries. This significant advancement relies on a clever reduction to locally testable codes (LTCs), capitalizing on recent breakthrough works in LTCs.

With ... more >>>


TR24-078 | 19th April 2024
Oded Goldreich

On the relaxed LDC of BGHSV: A survey that corrects the record

Revisions: 1

A locally decodable code (LDC) is an error correcting code that allows for recovery of any desired bit in the message based on a constant number of randomly selected bits in the possibly corrupted codeword.
A relaxed LDC requires correct recovery only in case of actual codewords, while requiring that ... more >>>




ISSN 1433-8092 | Imprint