TY - JOUR

T1 - Np-hardness of reed–solomon decoding, and the prouhet–tarry–escott problem

AU - Gandikota, Venkata

AU - Ghazi, Badih

AU - Grigorescu, Elena

N1 - Funding Information:
The first author was supported in part by a grant from the Purdue Research Foundation and by NSF CCF-1649515. The second author was supported in part by NSF STC award CCF 0939370 and NSF awards CCF-1217423, CCF-1420956, CCF-1420692, and CCF-1217423. The third author was supported in part by NSF CCF-1649515.
Funding Information:
∗Received by the editors November 16, 2016; accepted for publication (in revised form) May 29, 2018; published electronically August 7, 2018. A preliminary version of this work appeared in the proceedings of ISIT’15 and FOCS’16. http://www.siam.org/journals/sicomp/47-4/M110349.html Funding: The first author was supported in part by a grant from the Purdue Research Foundation and by NSF CCF-1649515. The second author was supported in part by NSF STC award CCF 0939370 and NSF awards CCF-1217423, CCF-1420956, CCF-1420692, and CCF-1217423. The third author was supported in part by NSF CCF-1649515. †Purdue University, West Lafayette, IN 47907 (vgandiko@purdue.edu, elena-g@purdue.edu). ‡Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139 (badih@mit.edu).

PY - 2018

Y1 - 2018

N2 - Establishing the complexity of bounded distance decoding for Reed–Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy [IEEE Trans. Inform. Theory, 51 (2005), pp. 2249–2256]. The problem is motivated by the large current gap between the regime when it is NP-hard and the regime when it is efficiently solvable (i.e., the Johnson radius). We show the first NP-hardness results for asymptotically smaller decoding radii than the maximum likelihood decoding radius of Guruswami and Vardy. Specifically, for Reed–Solomon codes of length N and dimension K = Θ(N), we show that it is NP-hard to decode more than N − K − clog log log N N errors (with c > 0 an absolute constant). Moreover, we show that the problem is NP-hard under quasi-polynomial-time reductions for an error amount > N − K − clog N (with c > 0 an absolute constant). An alternative natural reformulation of the bounded distance decoding problem for Reed–Solomon codes is as a polynomial reconstruction problem. In this view, our results show that it is NP-hard to decide whether there exists a degree K polynomial passing through K + clog log N log N points from a given set of points (a1, b1), (a2, b2) . . ., (aN, bN). Furthermore, it is NP-hard under quasi-polynomial-time reductions to decide whether there is a degree K polynomial passing through K+clog N many points. These results follow from the NP-hardness of a generalization of the classical subset sum problem to higher moments, called moments subset sum, which has been a known open problem, and which May be of independent interest. We further reveal a strong connection with the well-studied Prouhet–Tarry–Escott problem in number theory, which turns out to capture a main Barrier in extending our techniques. We believe the Prouhet–Tarry–Escott problem deserves further study in the theoretical computer science community.

AB - Establishing the complexity of bounded distance decoding for Reed–Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy [IEEE Trans. Inform. Theory, 51 (2005), pp. 2249–2256]. The problem is motivated by the large current gap between the regime when it is NP-hard and the regime when it is efficiently solvable (i.e., the Johnson radius). We show the first NP-hardness results for asymptotically smaller decoding radii than the maximum likelihood decoding radius of Guruswami and Vardy. Specifically, for Reed–Solomon codes of length N and dimension K = Θ(N), we show that it is NP-hard to decode more than N − K − clog log log N N errors (with c > 0 an absolute constant). Moreover, we show that the problem is NP-hard under quasi-polynomial-time reductions for an error amount > N − K − clog N (with c > 0 an absolute constant). An alternative natural reformulation of the bounded distance decoding problem for Reed–Solomon codes is as a polynomial reconstruction problem. In this view, our results show that it is NP-hard to decide whether there exists a degree K polynomial passing through K + clog log N log N points from a given set of points (a1, b1), (a2, b2) . . ., (aN, bN). Furthermore, it is NP-hard under quasi-polynomial-time reductions to decide whether there is a degree K polynomial passing through K+clog N many points. These results follow from the NP-hardness of a generalization of the classical subset sum problem to higher moments, called moments subset sum, which has been a known open problem, and which May be of independent interest. We further reveal a strong connection with the well-studied Prouhet–Tarry–Escott problem in number theory, which turns out to capture a main Barrier in extending our techniques. We believe the Prouhet–Tarry–Escott problem deserves further study in the theoretical computer science community.

KW - Bounded distance decoding

KW - Polynomial reconstruction

KW - Prouhet–Tarry–Escott problem

KW - Reed–Solomon decdoing

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

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

U2 - 10.1137/16M110349X

DO - 10.1137/16M110349X

M3 - Article

AN - SCOPUS:85053609912

VL - 47

SP - 1547

EP - 1584

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 4

ER -