NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem

Venkata Gandikota, Badih Ghazi, Elena Grigorescu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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. Inf. Theory, 2005). 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 = O(N), we show that it is NP-hard to decode more than N-K-O/log N log log N) errors. Moreover, we show that the problem is NP-hard under quasipolynomial-time reductions for an error amount > N-K-c log 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 + O/log N log log N) points from a given set of points (a1, b1), (a2, b2)..., (aN, bN). Furthermore, it is NP-hard under quasipolynomial-time reductions to decide whether there is a degree K polynomial passing through K + c logN many points (with c > 0 an absolute constant). 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 languageEnglish (US)
Title of host publicationProceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
PublisherIEEE Computer Society
Pages760-769
Number of pages10
ISBN (Electronic)9781509039333
DOIs
StatePublished - Dec 14 2016
Externally publishedYes
Event57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, United States
Duration: Oct 9 2016Oct 11 2016

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2016-December
ISSN (Print)0272-5428

Conference

Conference57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
CountryUnited States
CityNew Brunswick
Period10/9/1610/11/16

Keywords

  • Bounded Distance Decoding
  • Moments Subset Sum
  • Reed-Solomon Codes

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem'. Together they form a unique fingerprint.

Cite this