Conjecture on the average number of punctures for GRS covering
Conjecture on the average number of punctures for GRS covering
Let be an generalized Reed–Solomon (GRS) code, and let denote the covering algorithm. The average number of punctures is the expected number of coordinates punctured before the algorithm succeeds in returning a codeword within the covering radius.
Puncture-count conjecture. For an GRS code, the average number of punctures needed for to succeed in returning a codeword within the covering radius is less than
\begin{cases} c_1(d-1) & \text{when } \operatorname{GRS\text{-}decode \text{ is a unique decoder},\\ c_2 & \text{when } \operatorname{GRS\text{-}decode}=\operatorname{GS} \text{ is the list decoder}, \end{cases}for some positive constants and .
The source later states that the first part does not hold in general; the second part remains unresolved there. Thus this combined conjecture is refuted, with its list-decoder component still open.
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.