Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > APPROXIMATE LOCALLY DECODABLE CODE:
Reports tagged with approximate locally decodable code:
TR23-056 | 26th April 2023
Geoffrey Mon, Dana Moshkovitz, Justin Oh

Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate

Revisions: 2

We present simple constructions of good approximate locally decodable codes (ALDCs) in the presence of a $\delta$-fraction of errors for $\delta<1/2$. In a standard locally decodable code $C \colon \Sigma_1^k \to \Sigma_2^n$, there is a decoder $M$ that on input $i \in [k]$ correctly outputs the $i$-th symbol of a ... more >>>




ISSN 1433-8092 | Imprint