Earlier Version

List-decodability with large radius for Reed-Solomon codes

Ferber A, Kwan MA, Sauermann L. 2022. List-decodability with large radius for Reed-Solomon codes. 62nd Annual IEEE Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science vol. 2022, 720–726.


Conference Paper | Published | English

Scopus indexed
Author
Ferber, Asaf; Kwan, Matthew AlanISTA; Sauermann, Lisa
Department
Abstract
List-decodability of Reed-Solomon codes has re-ceived a lot of attention, but the best-possible dependence between the parameters is still not well-understood. In this work, we focus on the case where the list-decoding radius is of the form r=1−ε for ε tending to zero. Our main result states that there exist Reed-Solomon codes with rate Ω(ε) which are (1−ε,O(1/ε) -list-decodable, meaning that any Hamming ball of radius 1−ε contains at most O(1/ε) codewords. This trade-off between rate and list-decoding radius is best-possible for any code with list size less than exponential in the block length. By achieving this trade-off between rate and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and Wootters, and resolve the main motivating question of their work. Moreover, while their result requires the field to be exponentially large in the block length, we only need the field size to be polynomially large (and in fact, almost-linear suffices). We deduce our main result from a more general theorem, in which we prove good list-decodability properties of random puncturings of any given code with very large distance.
Publishing Year
Date Published
2022-02-01
Proceedings Title
62nd Annual IEEE Symposium on Foundations of Computer Science
Volume
2022
Page
720-726
Conference
FOCS: Symposium on Foundations of Computer Science
Conference Location
Denver, CO, United States
Conference Date
2022-02-07 – 2022-02-10
ISSN
IST-REx-ID

Cite this

Ferber A, Kwan MA, Sauermann L. List-decodability with large radius for Reed-Solomon codes. In: 62nd Annual IEEE Symposium on Foundations of Computer Science. Vol 2022. IEEE; 2022:720-726. doi:10.1109/FOCS52979.2021.00075
Ferber, A., Kwan, M. A., & Sauermann, L. (2022). List-decodability with large radius for Reed-Solomon codes. In 62nd Annual IEEE Symposium on Foundations of Computer Science (Vol. 2022, pp. 720–726). Denver, CO, United States: IEEE. https://doi.org/10.1109/FOCS52979.2021.00075
Ferber, Asaf, Matthew Alan Kwan, and Lisa Sauermann. “List-Decodability with Large Radius for Reed-Solomon Codes.” In 62nd Annual IEEE Symposium on Foundations of Computer Science, 2022:720–26. IEEE, 2022. https://doi.org/10.1109/FOCS52979.2021.00075.
A. Ferber, M. A. Kwan, and L. Sauermann, “List-decodability with large radius for Reed-Solomon codes,” in 62nd Annual IEEE Symposium on Foundations of Computer Science, Denver, CO, United States, 2022, vol. 2022, pp. 720–726.
Ferber A, Kwan MA, Sauermann L. 2022. List-decodability with large radius for Reed-Solomon codes. 62nd Annual IEEE Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations of Computer Science vol. 2022, 720–726.
Ferber, Asaf, et al. “List-Decodability with Large Radius for Reed-Solomon Codes.” 62nd Annual IEEE Symposium on Foundations of Computer Science, vol. 2022, IEEE, 2022, pp. 720–26, doi:10.1109/FOCS52979.2021.00075.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2012.10584

Search this title in

Google Scholar
ISBN Search