This is a research-expository paper. It deals with
complexity issues in the theory of linear block codes. The main
emphasis is on the theoretical performance limits of the
best known codes. Therefore, the main subject of the paper are
families of asymptotically good codes, i.e., codes whose rate and
relative ... more >>>

We construct binary linear codes that are efficiently list-decodable
up to a fraction $(1/2-\eps)$ of errors. The codes encode $k$ bits
into $n = {\rm poly}(k/\eps)$ bits and are constructible and
list-decodable in time polynomial in $k$ and $1/\eps$ (in
particular, in our results $\eps$ need ... more >>>