Computer Science/Discrete Mathematics Seminar II

Reed–Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps

Understanding the limits of list-decodability of Reed–Solomon (RS) codes has been one of the most important open problems in algebraic coding theory. In the RS list-decoding problem, we are given $n$ distinct points $a_1, \ldots, a_n$ in a finite field $\mathbb{F}$ and a received word $(y_1, \ldots, y_n) \in \mathbb{F}^n$. The goal is to find all polynomials $P \in \mathbb{F}[X]$ of degree at most $k$ that agree with the received word on at least $A$ points, i.e., $P(a_i) = y_i$ for at least $A$ indices $i$. The central question is how small the agreement $A$ can be while the list of such polynomials stays polynomially small and can be found efficiently. RS codes are said to be list-decodable up to capacity if this is possible for $A = (1+\epsilon)k$, for every $\epsilon > 0$.

Recently, in a remarkable breakthrough, Brakensiek, Chen, Putterman, Zhang, and Zheng showed that RS codes over fields of large characteristic are algorithmically list-decodable all the way up to capacity. Building on this result, Jeronimo subsequently extended these techniques to resolve the proximity-gaps question for RS codes.

In this talk, I’ll give a transparent exposition of these results, with an emphasis on explaining why the approach works. I’ll compare these results with previous approaches and give a complete proof of the algorithmic list-decodability result. Time permitting, I’ll also discuss the extension to the proximity-gaps problem.

Based on joint work with Mrinal Kumar and Ramprasad Saptharishi.

Date & Time

November 17, 2026 | 11:30am – 12:30pm
Add to calendar 11/17/2026 11:30 11/17/2026 12:30 Computer Science/Discrete Mathematics Seminar II use-title Topic: Reed–Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps Speakers: Prahladh Harsha, Tata Institute of Fundamental Research More: https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-seminar-ii-631 Understanding the limits of list-decodability of Reed–Solomon (RS) codes has been one of the most important open problems in algebraic coding theory. In the RS list-decoding problem, we are given $n$ distinct points $a_1, \ldots, a_n$ in a finite field $\mathbb{F}$ and a received word $(y_1, \ldots, y_n) \in \mathbb{F}^n$. The goal is to find all polynomials $P \in \mathbb{F}[X]$ of degree at most $k$ that agree with the received word on at least $A$ points, i.e., $P(a_i) = y_i$ for at least $A$ indices $i$. The central question is how small the agreement $A$ can be while the list of such polynomials stays polynomially small and can be found efficiently. RS codes are said to be list-decodable up to capacity if this is possible for $A = (1+\epsilon)k$, for every $\epsilon > 0$. Recently, in a remarkable breakthrough, Brakensiek, Chen, Putterman, Zhang, and Zheng showed that RS codes over fields of large characteristic are algorithmically list-decodable all the way up to capacity. Building on this result, Jeronimo subsequently extended these techniques to resolve the proximity-gaps question for RS codes. In this talk, I’ll give a transparent exposition of these results, with an emphasis on explaining _WHY_ the approach works. I’ll compare these results with previous approaches and give a complete proof of the algorithmic list-decodability result. Time permitting, I’ll also discuss the extension to the proximity-gaps problem. Based on joint work with Mrinal Kumar and Ramprasad Saptharishi. Simonyi 101 and Remote Access a7a99c3d46944b65a08073518d638c23

Location

Simonyi 101 and Remote Access

Speakers

Prahladh Harsha, Tata Institute of Fundamental Research