cs.IT math.CO math.IT
Improved List Decodability of Reed Solomon Codes via Tree Packings. 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 epsilon in (0,1 there exist RS codes with rate Omega( frac epsilon log(1 epsilon) 1 ) that are list decodable from radius of 1 epsilon . 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.