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 not be constant and ... more >>>