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 ๐ distinct points ๐1,โฆ,๐๐ in a finite field ๐ฝ and a received word (๐ฆ1,โฆ,๐ฆ๐)โ๐ฝ๐. The goal is to find all polynomials ๐โ๐ฝ[๐] of degree at most ๐ that agree with the received word on at least ๐ด points, i.e., ๐(๐๐)=๐ฆ๐ for at least ๐ด indices ๐. The central question is how small the agreement ๐ด 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 ๐ด=(1+๐)๐, for every ๐ greater than 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.