Conjecture on puncture complexity and covering radius for fixed-rate GRS codes

Let C{\mathcal C} be an [n,k,d]q[n,k,d]_q generalized Reed–Solomon (GRS) code of fixed rate RR, let GRS-cover\operatorname{GRS\text{-}cover} be the covering algorithm, let GS\operatorname{GS} be the Guruswami–Sudan list decoder, and write ρH(C)\rho_{\mathrm H}({\mathcal C}) for the Hamming covering radius of C{\mathcal C}. The notation Θ(ρH(C))\Theta(\rho_{\mathrm H}({\mathcal C})) means that the average number of punctures is bounded above and below by positive constant multiples of this covering radius.

Fixed-rate puncture conjecture. For an [n,k,d]q[n,k,d]_q GRS code C{\mathcal C} of fixed rate RR, the average number of punctures needed for GRS-cover\operatorname{GRS\text{-}cover} to succeed with GRS-decode=GS\operatorname{GRS\text{-}decode}=\operatorname{GS} is

Θ(ρH(C)).\Theta\bigl(\rho_{\mathrm H}({\mathcal C})\bigr).

The source presents this as a proposed modification of the list-decoder part of the earlier conjecture. It is not resolved in the supplied text.

Sources & referencesView supporting material

Primary source

Samin Riasat and Hessam Mahdavifar, “Covering in Hamming and Grassmann Spaces: New Bounds and Reed–Solomon-Based Constructions”, arXiv:2512.22911 (2026).

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.