We construct binary linear codes that are efficiently list-decodable up to a fraction (1/2 - ε) of errors. 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, in our results ε 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/ε for such codes. Specifically, we are able to achieve n ≤ O(k{sup}3/ε{sup}(3+γ)) or, if a linear dependence on k is required, n ≤ O(k/ε{sup}(5+γ)), where γ > 0 is an arbitrary constant. The best previously known constructive bounds in this setting were n ≤ O(k{sup}2/ε{sup}4) and n ≤ O(k/ε{sup}6). Non-constructively, a random linear encoding of length n = O(k/ε{sup}2) suffices, but no sub-exponential algorithm is known for list decoding random codes. Our construction with a cubic dependence on ε is obtained by concatenating the recent Parvaresh-Vardy (PV) codes with dual BCH codes, and crucially exploits the soft decoding algorithm for PV codes. This result yields better hardness results for the problem of approximating NP witnesses in the model of Kumar and Sivakumar. Our result with the linear dependence on k is based on concatenation of the PV code with an arbitrary inner code of good minimum distance. In addition to being a basic question in coding theory, codes that are list-decodable from a fraction (1/2-ε)of errors for ε → 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-ε, 1/2+ε); this ε-biased property is a fundamental notion in pseudorandomness.
展开▼
