Name
Abstract | ||
|---|---|---|
The list-decodability of random linear codes is shown to be as good as that of general random codes. Specifically, for every fixed finite field Fq, p ∈ (0,1 - 1/q) and ε >; 0, it is proved that with high probability a random linear code C in Fqn of rate (1-Hq(p)-ε) can be list decoded from a fraction p of errors with lists of size at most O(1/ε). This also answers a basic open question concerning the existence of highly list-decodable linear codes, showing that a list-size of O(1/ε) suffices to have rate within ε of the information-theoretically optimal rate of 1 - Hq(p). The best previously known list-size bound was qO(1/ε) (except in the q = 2 case where a list-size bound of O(1/ε) was known). The main technical ingredient in the proof is a strong upper bound on the probability that I random vectors chosen from a Hamming ball centered at the origin have too many (more than Ω(ℓ)) vectors from their linear span also belong to the ball. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/TIT.2010.2095170 | IEEE Transactions on Information Theory |
Keywords | DocType | Volume |
linear span,hamming ball,high probability,basic open question,random linear codes,random linear code,list decoding capacity,linear codes,list-decodable linear code,information-theoretically optimal rate,fixed finite field,fraction p,probabilistic method,l random vector,random vector,general random code,list error-correction,finite field,information theory,linear code,computer and information science,list decoding,upper bound | Conference | 57 |
Issue | ISSN | Citations |
2 | 0018-9448 | 18 |
PageRank | References | Authors |
1.00 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Guruswami | 1 | 3205 | 247.96 |
| Johan Håstad | 2 | 3586 | 557.23 |
| Swastik Kopparty | 3 | 384 | 32.89 |