Conjecture on puncture complexity and covering radius for fixed-rate GRS codes
Conjecture on puncture complexity and covering radius for fixed-rate GRS codes
Let be an generalized Reed–Solomon (GRS) code of fixed rate , let be the covering algorithm, let be the Guruswami–Sudan list decoder, and write for the Hamming covering radius of . The notation 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 GRS code of fixed rate , the average number of punctures needed for to succeed with is
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
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.