Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Geoffrey Mon:

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-056 | 26th April 2023
Geoffrey Mon, Dana Moshkovitz, Justin Oh

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

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