Theory Seminar

On the Decodability of Primitive Reed-Solomon Codes

Qi Cheng

University of Oklahoma
Friday, February 08, 2013
10:00am - 11:00am
411 West Hall

Add to Google Calendar

About the Event

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.

Additional Information

Sponsor(s): EECS

Open to: Public