Average puncture bound for covering with Reed–Solomon codes

Let CC be an [n,k,d]q[n,k,d]_q generalized Reed–Solomon (GRS) code, and consider the covering algorithm that repeatedly punctures the received word and applies a GRS decoder. Let c1,c2c_1,c_2 be positive constants with c1,c2<1c_1,c_2<1. Average puncture conjecture. The average number of punctures needed for the algorithm to return a codeword within the covering radius is less than c1(d1)c_1(d-1) when the GRS decoder is a unique decoder, and less than c2c_2 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

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.