TH4.R8.1

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

Geoffrey Mon, Dana Moshkovitz, Justin Oh, University of Texas at Austin, United States

Session:
Topics in Modern Coding Theory 3

Track:
2: Modern Coding Theory

Location:
Omega

Presentation Time:
Thu, 11 Jul, 16:25 - 16:45

Session Chair:
David Mitchell,
Abstract
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)$.
Resources