On the Decodability of Primitive Reed-Solomon Codes

Reed-Solomon codes are (list-)decodable up to the Johnson-Guruswami-Sudan bound. No polynomial time decoding algorithm is known when number of errors is larger than the JGS bound. The maximum likely-hood decoding of generalized Reed-Solomon codes is NP-hard, but it appears hard to establish complexity results for the primitive Reed-Solomon codes. In this talk, I will present several results on this problem. I will also talk about the deterministic construction of small Hamming balls containing many Reed-Solomon codewords.