ECCC-Report TR10-003https://eccc.weizmann.ac.il/report/2010/003Comments and Revisions published for TR10-003en-usWed, 06 Jan 2010 05:30:06 +0200
Paper TR10-003
| On the List-Decodability of Random Linear Codes |
Venkatesan Guruswami,
Johan HÃ¥stad,
Swastik Kopparty
https://eccc.weizmann.ac.il/report/2010/003 For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\varepsilon >
0$, we prove that with high probability a random subspace $C$ of
$\F_q^n$ of dimension $(1-H_q(p)-\varepsilon)n$ has the
property that every Hamming ball of radius $pn$ has at most
$O(1/\varepsilon)$ codewords.
This answers a basic open question concerning the list-decodability
of linear codes, showing that a list size of $O(1/\varepsilon)$
suffices to have rate within $\varepsilon$ of the ``capacity''
$1-H_q(p)$. This matches up to constant factors the list-size
achieved by general random codes, and gives an exponential improvement
over the best previously known list-size bound of $q^{O(1/\varepsilon)}$.
The main technical ingredient in our proof is a strong upper bound
on the probability that $\ell$ random vectors chosen from a Hamming
ball centered at the origin have too many (more than $\Theta(\ell)$)
vectors from their linear span also belong to the ball.
Wed, 06 Jan 2010 05:30:06 +0200https://eccc.weizmann.ac.il/report/2010/003