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 message $x$ (with high probability) using only $q$ queries to a given string $w$ that is $\delta$-close to $C(x)$. In an ALDC, the decoder $M$ only needs to be correct on a $1-\epsilon$ fraction of $i\in [k]$ for $\epsilon$ much smaller than $\delta$. We present a construction of explicit ALDCs for all constants $1/2 > \delta > \epsilon$ with a constant number of queries $q$ and with constant, near-optimal rate. Standard LDCs with constant number of queries and \emph{any} constant rate are known to be impossible.

We additionally explore what is the lowest error probability $\epsilon$ one can achieve for fixed $\delta$ and $q$. We show that for any ALDC, $\epsilon = \Omega(\delta^{\lceil q/2\rceil})$. We then show that there exist explicit constant rate ALDCs for any constant $q$ that achieve $\epsilon = O(\delta^{\lceil q/2\rceil})$. In particular, for $q = 3$, we have a constant rate ALDC with error probability $\epsilon = O(\delta^2)$.

Correct abstract parsing issue

We present simple constructions of good approximate locally decodable codes (ALDCs) in the presence of a $\delta$-fraction of errors for $\delta \delta > \epsilon$ with a constant number of queries $q$ and with constant, near-optimal rate. Standard LDCs with constant number of queries and \emph{any} constant rate are known to be impossible.

We additionally explore what is the lowest error probability $\epsilon$ one can achieve for fixed $\delta$ and $q$. We show that for any ALDC, $\epsilon = \Omega(\delta^{\lceil q/2\rceil})$. We then show that there exist explicit constant rate ALDCs for any constant $q$ that achieve $\epsilon = O(\delta^{\lceil q/2\rceil})$. In particular, for $q = 3$, we have a constant rate ALDC with error probability $\epsilon = O(\delta^2)$.

Updated for ISIT 2024

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 message $x$ (with high probability) using only $q$ queries to a given string $w$ that is $\delta$-close to $C(x)$. In an ALDC, the decoder $M$ only needs to be correct on $1-\epsilon$ fraction of $i\in [k]$ for $\epsilon$ much smaller than $\delta$. We present a construction of explicit ALDCs for all constants $1/2>\delta>\epsilon$ 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. Past constructions of ALDCs had vanishingly small rate or a large super-constant number of queries.

Our constructions can be adapted to admit a weak notion of list decoding. In a weak approximate locally list decodable code $C \colon \Sigma_1^k \to \Sigma_2^n$, there is a decoder $M$ that on input $i \in [k]$, makes at most $q$ queries to a string $w \in \Sigma_2^n$ and outputs a list of symbols $M(i) \subset \Sigma_1$ with $|M(i)| \ll |\Sigma_1|$. For any codeword $C(x)$ that is $\delta$-close to $w$, $x_i \in M(i)$ for at least $1-\epsilon$ fraction of $i \in [k]$. We provide constructions of weak approximate locally list decodable codes with a constant number of queries and with rate approaching that of random (standard) list decodable codes.

We additionally explore what is the lowest error probability $\epsilon$ one can achieve for fixed $\delta$ and $q$. We show that for any ALDC, $\epsilon = \Omega(\delta^{\lceil q/2\rceil})$. We then show that there exist explicit constant rate ALDCs for any constant $q$ that achieve $\epsilon = O(\delta^{\lceil q/2\rceil})$. In particular, for $q = 3$, we have a constant rate ALDC with error probability $\epsilon = O(\delta^2)$.