Randomly punctured reed-solomon codes achieve the list decoding capacity over polynomial-size alphabets
This paper shows that, with high probability, randomly punctured Reed-Solomon codes over
fields of polynomial size achieve the list decoding capacity. More specifically, we prove that …
fields of polynomial size achieve the list decoding capacity. More specifically, we prove that …
Generalized GM-MDS: Polynomial Codes are Higher Order MDS
J Brakensiek, M Dhar, S Gopi - Proceedings of the 56th Annual ACM …, 2024 - dl.acm.org
The GM-MDS theorem, conjectured by Dau-Song-Dong-Yuen and proved by Lovett and
Yildiz-Hassibi, shows that the generator matrices of Reed-Solomon codes can attain every …
Yildiz-Hassibi, shows that the generator matrices of Reed-Solomon codes can attain every …
AG codes achieve list decoding capacity over constant-sized fields
The recently-emerging field of higher order MDS codes has sought to unify a number of
concepts in coding theory. Such areas captured by higher order MDS codes include …
concepts in coding theory. Such areas captured by higher order MDS codes include …
Improved field size bounds for higher order MDS codes
J Brakensiek, M Dhar, S Gopi - IEEE Transactions on …, 2024 - ieeexplore.ieee.org
Higher order MDS codes are an interesting generalization of MDS codes recently introduced
by Brakensiek et al.,(2023). In later works, they were shown to be intimately connected to …
by Brakensiek et al.,(2023). In later works, they were shown to be intimately connected to …
Improved list-decodability and list-recoverability of Reed–Solomon codes via tree packings
This paper shows that there exist Reed–Solomon (RS) codes, over exponentially large finite
fields in the code length, that are combinatorially list-decodable well beyond the Johnson …
fields in the code length, that are combinatorially list-decodable well beyond the Johnson …
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets
A simple, recently observed generalization of the classical Singleton bound to list-decoding
asserts that rate R codes are not list-decodable using list-size L beyond an error fraction …
asserts that rate R codes are not list-decodable using list-size L beyond an error fraction …
Random reed-solomon codes achieve the half-singleton bound for insertions and deletions over linear-sized alphabets
In this paper, we prove that with high probability, random Reed-Solomon codes approach
the half-Singleton bound-the optimal rate versus error tradeoff for linear insdel codes-with …
the half-Singleton bound-the optimal rate versus error tradeoff for linear insdel codes-with …
Fast list decoding of univariate multiplicity and folded Reed-Solomon codes
We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-
Solomon (FRS) codes can be made to run in ̃O(n) time. Univariate multiplicity codes and …
Solomon (FRS) codes can be made to run in ̃O(n) time. Univariate multiplicity codes and …
Pseudorandom linear codes are list decodable to capacity
AL Putterman, E Pyne - arXiv preprint arXiv:2303.17554, 2023 - arxiv.org
We introduce a novel family of expander-based error correcting codes. These codes can be
sampled with randomness linear in the block-length, and achieve list-decoding capacity …
sampled with randomness linear in the block-length, and achieve list-decoding capacity …
Randomness-Efficient Constructions of Capacity-Achieving List-Decodable Codes
In this work, we consider the task of generating list-decodable codes over small (say, binary)
alphabets using as little randomness as possible. Specifically, we hope to generate codes …
alphabets using as little randomness as possible. Specifically, we hope to generate codes …