Average puncture bound for covering with Reed–Solomon codes
Let be an generalized Reed–Solomon (GRS) code, and consider the covering algorithm that repeatedly punctures the received word and applies a GRS decoder. Let be positive constants with . Average puncture conjecture. The average number of punctures needed for the algorithm to return a codeword within the covering radius is less than when the GRS decoder is a unique decoder, and less than when it is the Guruswami–Sudan list decoder. This conjecture concerns the average-case complexity of the covering algorithm; the supplied text gives empirical data as motivation but does not state a resolution, so the claim remains open.
References
Primary source
Samin Riasat and Hessam Mahdavifar, “Efficient Covering Using Reed–Solomon Codes”, arXiv:2502.01984 (2025).
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
No solutions have been posted yet.