Soft Decoding, Dual BCH Codes, and Better List-Decodable $varepsilon$-Biased Codes

摘要

Explicit constructions of binary linear codes that are efficiently list-decodable up to a fraction $(1/2-varepsilon)$ of errors are given. The codes encode $k$ bits into $n = {rm poly}(k/varepsilon)$ bits and are constructible and list-decodable in time polynomial in $k$ and $1/varepsilon$ (in particular, $varepsilon$ 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/varepsilon$ for such codes. Specifically, they are able to achieve $n leqslant O(k^3/varepsilon^{3+gamma})$ or, if a linear dependence on $k$ is required, $n leqslant mathtilde{O}(k/varepsilon^{5+gamma})$ , where $gamma > 0$ is an arbitrary constant. The best previously known constructive bounds in this setting were $n leqslant O(k^2/varepsilon^4)$ and $n leqslant O(k/varepsilon^6)$ . Nonconstructively, a random linear encoding of length $n = O(k/varepsilon^2)$ 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-varepsilon)$ of errors for $varepsilon to 0$ are important in several complexity theory applications. For example, the construction with near-cubic dependence on $varepsilon$ yields better hardness results for the problem of approximating ${ssr NP}$ witnesses. Further, the codes constructed have the property that all nonzero codewords have relative Hamming weights in the range $(1/2-varepsilon, 1/2+varepsilon)$ ; this $varepsilon$-biased property is a fundamental notion in pseudorandomness.