Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-003 | 6th January 2010 05:09

On the List-Decodability of Random Linear Codes


Authors: Venkatesan Guruswami, Johan Hastad, Swastik Kopparty
Publication: 6th January 2010 05:30
Downloads: 1579


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.

ISSN 1433-8092 | Imprint