Generic Reed-Solomon codes achieve list-decoding capacity

DOI10.1145/3564246.3585128MaRDI QIDQ6401724zbMATH OpenFDO

Authors Joshua Brakensiek, Sivakanth Gopi, Visu Makam

Publication date 10 June 2022

Full work available at URL https://doi.org/10.1145/3564246.3585128

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: In a recent paper, Brakensiek, Gopi and Makam introduced higher order MDS codes as a generalization of MDS codes. An order-$ell$ MDS code, denoted by $operatornameMDS(ell)$, has the property that any $ell$ 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 $operatornameMDS(ell)$ for all $ell$, 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-epsilon$ with list size at most $frac1-R-epsilonepsilon$, resolving a conjecture of Shangguan and Tamo.

Cited in

(3)

• A criterion for decoding on the binary symmetric channel
• Kapranov degrees
• Point-polynomial incidences theorem with an application to Reed-Solomon codes

This page was built for publication: Generic Reed-Solomon codes achieve list-decoding capacity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6401724)