Soft Decoding, Dual BCH Codes, and Better List-Decodable epsilon-Biased Codes
Explicit constructions of binary linear codes that are efficiently list-decodable up to a fraction (1/2 - epsilon) of errors are given. The codes encode k bits into n = poly(k/epsilon) bits and are constructible and list-decodable in time polynomial in k and 1/epsilon ( in particular, epsilon 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/epsilon for such codes. Specifically, they are able to achieve n   0 is an arbitrary constant. The best previously known constructive bounds in this setting were n   0 are important in several complexity theory applications. For example, the construction with near-cubic dependence on epsilon 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 - epsilon, 1/2 + epsilon); this epsilon-biased property is a fundamental notion in pseudorandomness.
soft decoding dual bch codes pseudorandomness code concatenation list decoding list recovery parvaresh-vardy codes