Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-070 | 7th May 2020 08:24

On the list recoverability of randomly punctured codes

RSS-Feed




Revision #1
Authors: Ben Lund, Aditya Potukuchi
Accepted on: 7th May 2020 08:24
Downloads: 503
Keywords: 


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.


Paper:

TR20-070 | 4th May 2020 05:02

On the list recoverability of randomly punctured codes





TR20-070
Authors: Ben Lund, Aditya Potukuchi
Publication: 4th May 2020 12:06
Downloads: 610
Keywords: 


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.



ISSN 1433-8092 | Imprint