Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate
Geoffrey Mon, Dana Moshkovitz, Justin Oh · 2024
We present simple constructions of good approxi-mate locally decodable codes (ALDCs) in the presence of a$\delta{-}$fraction of errors for$\delta \delta > \varepsilon$with a constant number of queries$q$and with constant, near-optimal rate. Standard LDCs with constant number of queries and any constant rate are known to be impossible. We additionally explore what is the lowest error probability$\varepsilon$one can achieve for fixed$\delta$and$q$. We show that for any ALDC,$\in=\Omega(\delta \mathrm{r}q/2\rceil)$. We then show that there exist explicit constant rate ALDCs for any constant$q$that achieve$\varepsilon=O(\delta^{\lceil q/2\rceil})$. In particular, for$q=3$, we have a constant rate ALDC with error probability$\varepsilon=O(\delta^{2})$. A full version of this paper is available at https://eccc.weizmann.ac.il/report/2023/056/.