@inproceedings{brakensiek2022generic,
author = {Brakensiek, Joshua and Gopi, Sivakanth and Makam, Visu},
title = {Generic Reed-Solomon codes achieve list-decoding capacity},
booktitle = {STOC 2023},
year = {2022},
month = {June},
abstract = {In a recent paper, Brakensiek, Gopi and Makam introduced higher order MDS codes as a generalization of MDS codes. An order-ℓ MDS code, denoted by MDS(ℓ), has the property that any ℓ subspaces formed from columns of its generator matrix intersect as minimally as possible. An independent work by Roth defined a different notion of higher order MDS codes as those achieving a generalized singleton bound for list-decoding. In this work, we show that these two notions of higher order MDS codes are (nearly) equivalent.
We also show that generic Reed-Solomon codes are MDS(ℓ) for all ℓ, relying crucially on the GM-MDS theorem which shows that generator matrices of generic Reed-Solomon codes achieve any possible zero pattern. As a corollary, this implies that generic Reed-Solomon codes achieve list decoding capacity. More concretely, we show that, with high probability, a random Reed-Solomon code of rate R over an exponentially large field is list decodable from radius 1−R−ϵ with list size at most (1−R−ϵ)/ϵ, resolving a conjecture of Shangguan and Tamo.},
url = {http://approjects.co.za/?big=en-us/research/publication/generic-reed-solomon-codes-achieve-list-decoding-capacity/},
}