Soft decoding, dual BCH codes, and better list-decodable ε-biased codes

Explicit constructions of binary linear codes that are efficiently list-decodable up to a fraction (1/2-ε) of errors are given. The codes encode k bits into n = poly(k/ε) bits and are constructible and list-decodable in time polynomial in k and 1/ε (in particular, ε need not be constant and can even be polynomially small in n). These results give the best known polynomial dependence of n on k and 1/ε for such codes. Specifically, they are able to achieve n ≤ O(k³\ ε^3+γ) or, if a linear dependence on k is required, n ≤ O k/ε^5+γ), where γ > 0 is an arbitrary constant. The best previously known constructive bounds in this setting were n ≤ O(k²/ε⁴) and n ≤ O(k/ε⁶). Nonconstructively, a random linear encoding of length n = O(k/ε ²) suffices, but no subexponential algorithm is known for list decoding random codes. In addition to being a basic question in coding theory, codes that are list-decodable from a fraction (1/2-ε of errors for ε to 0 are important in several complexity theory applications. For example, the construction with near-cubic dependence on ε yields better hardness results for the problem of approximating NP witnesses. Further, the codes constructed have the property that all nonzero codewords have relative Hamming weights in the range (1/2-ε, 1/2+ε ; this ε-biased property is a fundamental notion in pseudorandomness.