期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-47
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 listdecoding 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.
