Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings

.This paper shows that there exist Reed–Solomon (RS) codes, over exponentially large finite fields in the code length, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving the list-decoding capacity. In particular, we show that for any \(\varepsilon \in (0,1]\) there exist RS codes with rate \(\Omega (\frac{\varepsilon }{\log (1/\varepsilon )+1})\) that are list-decodable from radius of \(1-\varepsilon\). We generalize this result to list-recovery, showing that there exist \((1 - \varepsilon, \ell, O(\ell/\varepsilon ))\)-list-recoverable RS codes with rate \(\Omega ( \frac{\varepsilon }{\sqrt{\ell } (\log (1/\varepsilon )+1)})\). 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. We also state a new conjecture that generalizes the tree packing theorem to hypergraphs and show that if this conjecture holds, then there would exist RS codes that are optimally (nonasymptotically) list-decodable.KeywordsNash-Williams–Tutte theoremMSC codes05C0505C6511T7194B0594B25