All reports by Author Geoffrey Mon:

__
TR23-093
| 29th June 2023
__

Vinayak Kumar, Geoffrey Mon#### Relaxed Local Correctability from Local Testing

Revisions: 1

__
TR23-056
| 26th April 2023
__

Geoffrey Mon, Dana Moshkovitz, Justin Oh#### Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate

Vinayak Kumar, Geoffrey Mon

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 >>>

Geoffrey Mon, Dana Moshkovitz, Justin Oh

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 >>>