Abstract: Reed-Solomon (RS) codes are among the most studied and widely used error-correcting codes, and decoding them efficiently is a central algorithmic challenge. In this talk, we survey the progression of decoding algorithms for RS codes and their variants, with a focus on achieving nearly linear running times.

We begin with the fundamentals: RS codes, the unique decoding problem, and classical algorithms such as Berlekamp-Massey and Welch-Berlekamp. We then move to list decoding, introducing the Johnson radius and the polynomial-time algorithms of Sudan (1997) and Guruswami-Sudan (1999), and briefly mention capacity-approaching list decoding via univariate multiplicity codes and folded Reed-Solomon codes.

The main focus of the talk is on obtaining nearly-linear-time versions of these algorithms. We will see a detailed proof that the Welch-Berlekamp algorithm can be made nearly linear, by using more efficient polynomial arithmetic algorithms such as polynomial division and GCD computation. We then briefly survey how analogous ideas yield nearly-linear-time algorithms for Sudan, Guruswami-Sudan, and beyond.

About the speaker: Prahladh Harsha is a Professor at the School of Technology and Computer Science at the Tata Institute of Fundamental Research (TIFR), Mumbai, India. He obtained his BTech degree in Computer Science and Engineering from IIT Madras in 1998 and his PhD in Computer Science from the Massachusetts Institute of Technology (MIT) in 2004. He has worked at Microsoft Research, TTI Chicago and has been at TIFR since 2010.

Prahladh’s research interests are in the area of theoretical computer science, with special emphasis on computational complexity theory and algebraic coding theory. He is best known for his work in the area of probabilistically checkable proofs. Prahladh Harsha is a recipient of the NASI Young Scientist Award for Mathematics and the Swarnajayanti Fellowship (Govt. of India).

Prof. Harsha has served on the editorial boards of SIAM Journal on Computing and Algorithmica. He is currently the Editor-in-Chief of the ACM Transactions on Computation Theory and a Fellow of the Indian Academy of Sciences.