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.