Soft Decoding, Dual BCH Codes, and Better List-Decodable varepsilon-Biased Codes.
Lists
Only you see this
Abstract
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 ≤ Õ(k <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> /ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3+γ</sup> ) or, if a linear dependence on k is required, n ≤ O(k/ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">5+γ</sup> ) , where γ >; 0 is an arbitrary constant. The best previously known constructive bounds in this setting were n ≤ O(k <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> /ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> ) and n ≤ O(k/ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">6</sup> ) . Nonconstructively, a random linear encoding of length n = O(k/ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) 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 ε → 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.
BibTeX
@article{guruswami2011soft,
author = {Venkatesan Guruswami and Atri Rudra},
title = {{Soft Decoding, Dual BCH Codes, and Better List-Decodable varepsilon-Biased Codes.}},
journal = {IEEE Trans. Information Theory},
year = {2011},
url = {https://openreview.net/forum?id=QRXsWbf7YO},
}Loading related content...