ECCC-Report TR20-168https://eccc.weizmann.ac.il/report/2020/168Comments and Revisions published for TR20-168en-usWed, 11 Nov 2020 19:06:16 +0200
Paper TR20-168
| Improved List-Decodability of Reedâ€“Solomon Codes via Tree Packings |
Zeyu Guo,
Ray Li,
Itzhak Tamo,
Mary Wootters,
Chong Shangguan
https://eccc.weizmann.ac.il/report/2020/168This 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.Wed, 11 Nov 2020 19:06:16 +0200https://eccc.weizmann.ac.il/report/2020/168