Title | ||
---|---|---|
Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings: [Extended Abstract] |
Abstract | ||
---|---|---|
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 ε E (0,1] there exist RS codes with rate $\Omega(\frac{\varepsilon}{1\not\varepsilon(1/_{\in})+1})$ that are list-decodable from radius of 1-ε. We ... |
Year | DOI | Venue |
---|---|---|
2021 | 10.1109/FOCS52979.2021.00074 | 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | ISSN |
Reed-Solomon codes,Computer science,Codes,Graph theory,Galois fields | Conference | 0272-5428 |
ISBN | Citations | PageRank |
978-1-6654-2055-6 | 0 | 0.34 |
References | Authors | |
0 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zeyu Guo | 1 | 0 | 0.34 |
Ray Li | 2 | 0 | 0.34 |
Chong Shangguan | 3 | 0 | 0.34 |
Itzhak Tamo | 4 | 548 | 36.05 |
Mary Wootters | 5 | 172 | 25.99 |