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.

Date

Speakers

Prahladh Harsha

Affiliation

Tata Institute of Fundamental Research