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 - Publisher Copyright:
© 2015 IEEE.
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 -