License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.30
URN: urn:nbn:de:0030-drops-126330
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12633/
Lund, Ben ;
Potukuchi, Aditya
On the List Recoverability of Randomly Punctured Codes
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.
BibTeX - Entry
@InProceedings{lund_et_al:LIPIcs:2020:12633,
author = {Ben Lund and Aditya Potukuchi},
title = {{On the List Recoverability of Randomly Punctured Codes}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {30:1--30:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-164-1},
ISSN = {1868-8969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12633},
URN = {urn:nbn:de:0030-drops-126330},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.30},
annote = {Keywords: List recovery, randomly punctured codes, Reed-Solomon codes}
}
|
Keywords: |
|
List recovery, randomly punctured codes, Reed-Solomon codes |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
11.08.2020 |
