
Reed–Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
Prahladh Harsha, of the Tata Institute of Fundamental Research, presents a seminar on the list-decodability of Reed-Solomon codes, given at the Institute for Advanced Study. The problem: given n points in a finite field and a received word, find all low-degree polynomials agreeing with that word on at least A positions, with the goal of decoding all the way up to capacity, where A equals (1+epsilon)k for any epsilon greater than zero. Harsha walks through the recent breakthrough by Brakensiek, Chen, Putterman, Zhang, and Zheng, which showed RS codes over large-characteristic fields are algorithmically list-decodable up to capacity, and Jeronimo's extension of those techniques to the proximity-gaps question. He compares the new approach to earlier methods and gives a complete proof of the algorithmic list-decoding result, time permitting also covering proximity gaps. The talk draws on joint work with Mrinal Kumar and Ramprasad Saptharishi and assumes familiarity with algebraic coding theory and polynomial algebra.