  Establishing the complexity of {\em 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- c\frac{\log N}{\log\log N}$
errors (with $c>0$ an absolute constant). 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).
  These results follow from the NP-hardness of a generalization of the
classical Subset Sum problem to higher moments, called {\em 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.
