## Abstract

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 − c_{log} ^{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 + c_{log} log N log N points from a given set of points (a1, b_{1}), (a2, b_{2}) . . ., (aN, b_{N}). 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.

Original language | English (US) |
---|---|

Pages (from-to) | 1547-1584 |

Number of pages | 38 |

Journal | SIAM Journal on Computing |

Volume | 47 |

Issue number | 4 |

DOIs | |

State | Published - 2018 |

Externally published | Yes |

## Keywords

- Bounded distance decoding
- Polynomial reconstruction
- Prouhet–Tarry–Escott problem
- Reed–Solomon decdoing

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics