Venkatesan Guruswami and Atri Rudra

We construct binary linear codes that are efficiently list-decodable up to a
fraction *(1/2-e)* of errors. The codes encode
*k* bits into *n =* poly(k/e) bits
and are constructible and list-decodable in time polynomial in *k* and
*1/e* (in particular, in our results *e* need not be constant and can even be polynomially small
in *n*). Our results give the best known polynomial dependence of *n*
on *k* and *1/e* for such codes.
Specifically, we are able to achieve *n ≤ O(k ^{3}/e^{3+g})* or, if a linear dependence
on

In addition to being a basic question in coding theory, codes that are
list-decodable from a fraction *(1/2-e)* of
errors for *e--> 0* have found many uses in
complexity theory. In addition, our codes have the property that all nonzero
codewords have relative Hamming weights in the range
*(1/2-e ,1/2+e)*; this*e-biased* property is a fundamental notion in
pseudorandomness.