Any (ρ, 2ρn+1, L)-list-recoverable code is a (ρ, L)-list-decodable insdel code, yielding the first polynomial-time insdel decoder for [n,k] Reed-Solomon codes with k > 2.
On the list recoverability of randomly punctured codes
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We show that a random puncturing of a code with good distance is list recoverable beyond the Johnson bound. In particular, this implies that there are Reed-Solomon codes that are list recoverable beyond the Johnson bound. It was previously known that there are Reed-Solomon codes that do not have this property. As an immediate corollary to our main theorem, we obtain better degree bounds on unbalanced expanders that come from Reed-Solomon codes.
fields
cs.IT 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Decoding Insertions/Deletions via List Recovery
Any (ρ, 2ρn+1, L)-list-recoverable code is a (ρ, L)-list-decodable insdel code, yielding the first polynomial-time insdel decoder for [n,k] Reed-Solomon codes with k > 2.