TY - GEN

T1 - On the NP-hardness of bounded distance decoding of Reed-Solomon codes

AU - Gandikota, Venkata

AU - Ghazi, Badih

AU - Grigorescu, Elena

N1 - Funding Information:
NSF STC Award CCF 0939370 and NSF award number CCF-1217423.

PY - 2015/9/28

Y1 - 2015/9/28

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84969899732&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84969899732&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2015.7282988

DO - 10.1109/ISIT.2015.7282988

M3 - Conference contribution

AN - SCOPUS:84969899732

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2904

EP - 2908

BT - Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - IEEE International Symposium on Information Theory, ISIT 2015

Y2 - 14 June 2015 through 19 June 2015

ER -