Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-036 | 14th March 2008 00:00

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


Authors: Venkatesan Guruswami, Atri Rudra
Publication: 23rd March 2008 13:31
Downloads: 3748


We construct binary linear codes that are efficiently list-decodable
up to a fraction $(1/2-\eps)$ of errors. The codes encode $k$ bits
into $n = {\rm poly}(k/\eps)$ bits and are constructible and
list-decodable in time polynomial in $k$ and $1/\eps$ (in
particular, in our results $\eps$ 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/\eps$ for such codes. Specifically, we are
able to achieve $n \le O(k^3/\eps^{3+\gamma})$ or, if a linear
dependence on $k$ is required, $n \le O(k/\eps^{5+\gamma})$, where
$\gamma > 0$ is an arbitrary constant. The best previously known
constructive bounds in this setting were $n \le O(k^2/\eps^4)$ and
$n \le O(k/\eps^6)$. Non-constructively, a random linear encoding of
length $n = O(k/\eps^2)$ suffices, but no sub-exponential algorithm
is known for list decoding random codes.

Our construction with a cubic dependence on $\eps$ 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

In addition to being a basic question in coding theory, codes that
are list-decodable from a fraction $(1/2-\eps)$ of errors for $\eps
\to 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-\eps ,1/2+\eps)$; this {\em
$\eps$-biased} property is a fundamental notion in

ISSN 1433-8092 | Imprint