Average puncture bound for covering with Reed–Solomon codes
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.