On the list recoverability of randomly punctured codes
Preprint
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.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov BoundIEEE Transactions on Information Theory, 2018
- Concentration of Measure for the Analysis of Randomized Algorithms2009
- Unbalanced expanders and randomness extractors from Parvaresh--Vardy codesJournal of the ACM, 2009
- Algorithmic Results in List DecodingFoundations and Trends® in Theoretical Computer Science, 2007
- Limits to List Decoding Reed–Solomon CodesIEEE Transactions on Information Theory, 2006