We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes with both constant alphabet and constant list sizes. More specifically, for any $R \in (0,1)$ and $\epsilon>0$, we give an algebraic construction of an infinite family of error-correcting codes of rate $R$, over an alphabet of size ... more >>>

A binary code $\text{Enc}:\{0,1\}^k \rightarrow \{0,1\}^n$ is $(\frac{1}{2}-\varepsilon,L)$-list decodable if for every $w \in \{0,1\}^n$, there exists a set $\text{List}(w)$ of size at most $L$, containing all messages $m \in \{0,1\}^k$ such that the relative Hamming distance between $\text{Enc}(m)$ and $w$ is at most $\frac{1}{2}-\varepsilon$.
A $q$-query local list-decoder is ... more >>>

Locally testable codes (LTC) are error-correcting codes that have a local tester which can distinguish valid codewords from words that are far from all codewords, by probing a given word only at a very small (sublinear, typically constant) number of locations. Such codes form the combinatorial backbone of PCPs. ... more >>>

Interactive oracle proofs (IOPs) are a hybrid between interactive proofs and PCPs. In an IOP the prover is allowed to interact with a verifier (like in an interactive proof) by sending relatively long messages to the verifier, who in turn is only allowed to query a few of the bits ... more >>>

We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieve list-decoding capacity. These are the first graph-based codes shown to have this property. Previously, the only codes known to achieve list-decoding capacity were completely random codes, random linear codes, and codes constructed by algebraic (rather than combinatorial) techniques. ... more >>>

We initiate the study of the role of erasures in local decoding and use our understanding to prove a separation between erasure-resilient and tolerant property testing. Local decoding in the presence of errors has been extensively studied, but has not been considered explicitly in the presence of erasures.

Motivated by ... more >>>