Deterministic list decoding of Reed-Solomon codes

Title of the Talk: Deterministic list decoding of Reed-Solomon codes
Host Faculty: Dr.Maria Francis
Speaker: Soham Chatterjee
Date: 9 July 2026
Time: 11:00 am
Venue: CSE LH3

Abstract
Reed-Solomon codes are obtained by evaluating all univariate polynomials of degree less than $k$ over a finite field $F$ on a fixed set of $n (> k$) distinct inputs. These codes are widely studied and used in theory and in practice, and are known to be optimal in certain settings of parameters. Given the central importance of these codes, the question of designing efficient decoding algorithms for these codes has been a problem of great interest for decades. The state of the art for this problem is given by results of Sudan and Guruswami-Sudan from the 1990s, which show that these codes can be decoded from $(n - \sqrt{nk})$ errors, either via a randomized algorithm in time $\text{poly}(n, \log |F|)$ or via a deterministic algorithm in time $\text{poly}(n, |F|)$.

In this talk, we will discuss a deterministic algorithm for decoding these codes from $(n - \sqrt{nk})$ errors in time $\text{poly}(n, \log

F

)$. At its core, the central problem we will look into is that of interpolating polynomials from noisy evaluations: given a set of input-output pairs, many of which are consistent with some low-degree polynomial, can we recover that polynomial or the set of all possible polynomials which agrees with the noisy evaluation in $\sqrt{nk}$ many locations efficiently and deterministically? The talk is based on joint work with Prahladh Harsha and Mrinal Kumar.

Bio

Soham Chatterjee is a second-year Integrated MSc-PhD student at the Tata Institute of Fundamental Research (TIFR), where he is advised by Prof. Mrinal Kumar. His research interests primarily lie in Computational Algebra, Error-Correcting Codes, Pseudorandomness, Complexity Theory, and Algorithms. He completed his Bachelor’s degree in Mathematics and Computer Science at the Chennai Mathematical Institute .