NP-Hardness of Bounded Distance Decoding for Reed–Solomon CodesResearch Paper
A Reed–Solomon code stores a message as the values of a low-degree polynomial at distinct points of a finite field. Decoding asks whether a received word is close to some codeword. The complexity of this question depends on how many errors are allowed, the field and the evaluation set. Unique decoding up to half the minimum distance and Guruswami–Sudan list…