Daqing Wan (UC Irvine)
On complexity of decoding Reed-Solomon codes

Abstract: The complexity of decoding the standard Reed-Solomon
code over a finite field Fq is a well known open problem
in coding theory. The only partial result in this direction
is a theorem of Cheng-Wan (FOCS, 2004) which says that in
certain cases, the decoding is at least as hard at the discrete
logarithm in a large extension of Fq. The main weakness of
this result is the assumption on q which implies that the
information rate goes to zero. In this talk, we will discuss
recent progress on removing the assumption and thus allowing
codes with arbitrary positive information rate (joint work
with Qi Cheng and with Jiyou Li).