On the NP-hardness of bounded distance decoding of Reed-Solomon codes
Venkata Gandikota, Badih Ghazi, Elena Grigorescu · 2015
Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005) show that given a Reed-Solomon code over a finite field F, of length n and dimension k, and given a target vector v ε Fn, it is NP-hard to decide if there is a codeword that disagrees with v on at most n - k - 1 coordinates. Understanding the complexity of this Bounded Distance Decoding problem as the amount of error in the target decreases is an important open problem in the study of Reed-Solomon codes. In this work, we extend the result of Guruswami and Vardy by proving that it is NP-hard to decide the existence of a codeword that disagrees with v on n - k - 2, and on n - k - 3 coordinates. No other NP-hardness results were known before for an amount of error <; n - k - 1. The core of our proofs is showing the NP-hardness of a parameterized generalization of the Subset-Sum problem to higher degrees (called Moments Subset-Sum) that may be of independent interest.