Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-168 | 11th November 2020 18:56

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


Authors: Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters
Publication: 11th November 2020 19:06
Downloads: 593


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.

ISSN 1433-8092 | Imprint