On the List-Decodability of Random Linear Codes
By Venkatesan Guruswami, J. Håstad, S. Kopparty. IEEE Transactions on Information Theory, 2010
462 citations recorded by the source corpus.
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 F<sub>q</sub>, <i>p</i> ∈ (0,1 - 1/<i>q</i>) and ε >; 0, it is proved that with high probability a random linear code <i>C</i> in F<sub>q</sub><sup>n</sup> of rate (1-<i>H</i><sub>q</sub>(<i>p</i>)-ε) can be list decoded from a fraction <i>p</i> of errors with lists of size at most <i>O</i>(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 - H<sub>q</sub>(p). The best previously known list-size bound was q<sup>O(1/ε)</sup> (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.
Subfields: Artificial Intelligence, Computer Networks and Communications, Molecular Biology
View Paper: https://www.semanticscholar.org/paper/c8c55be6487dbb39cbd4c54502f77ca243e0db04
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Molecular Biology
Citations in the corpus
- Introductory programming: a systematic literature review (2018, background): “The object-oriented paradigm appears to dominate the field, and many papers offer guidelines for teaching within that paradigm [18, 82, 133, 379].”