Random puncturing conjecture for list recovery of Reed–Solomon codes
Random puncturing conjecture for list recovery of Reed–Solomon codes
Let be fixed, and consider the degree- Reed–Solomon code with evaluation set . A random puncturing is obtained by retaining a random subset of evaluation coordinates, and the resulting code has its usual rate and list-recovery parameters. Random puncturing conjecture. The degree- Reed–Solomon code with evaluation set can be randomly punctured to rate
so that it is -list recoverable with high probability. This conjecture proposes that the logarithmic-in- rate is essentially the best possible rate for random puncturing while retaining list recoverability with list size proportional to and agreement parameter .
Sources & referencesView supporting material
Primary source
Ben Lund and Aditya Potukuchi, “On the list recoverability of randomly punctured codes”, arXiv:2005.02478 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.