Improved List-Decodability of Reed–Solomon Codes via Tree Packings
share
This paper shows that there exist Reed–Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any ϵ∈ (0,1] there exist RS codes with rate Ω(ϵ/log(1/ϵ)+1) that are list-decodable from radius of 1-ϵ. We generalize this result to obtain a similar result on list-recoverability of RS codes. Along the way we use our techniques to give a new proof of a result of Blackburn on optimal linear perfect hash matrices, and strengthen it to obtain a construction of strongly perfect hash matrices. To derive the results in this paper we show a surprising connection of the above problems to graph theory, and in particular to the tree packing theorem of Nash-Williams and Tutte. En route to our results on RS codes, we prove a generalization of the tree packing theorem to hypergraphs (and we conjecture that an even stronger generalization holds). We hope that this generalization to hypergraphs will be of independent interest.
READ FULL TEXT