Maximum-likelihood decoding of Reed-Solomon codes is NP-hard.

Venkatesan Guruswami, Alexander Vardy

Browse the full SODA paper archive.