Random puncturing conjecture for list recovery of Reed–Solomon codes

Let dd be fixed, and consider the degree-dd Reed–Solomon code with evaluation set FbbFqFbbF_q. 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-dd Reed–Solomon code with evaluation set FbbFqFbbF_q can be randomly punctured to rate

Ωd(1logq)\Omega_d\left(\frac{1}{\log q}\right)

so that it is (Ω(q),1/2)(\Omega(q),1/2)-list recoverable with high probability. This conjecture proposes that the logarithmic-in-qq rate is essentially the best possible rate for random puncturing while retaining list recoverability with list size proportional to qq and agreement parameter 1/21/2.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.