[Proof Complexity] BARC/MIAO seminar Tue Oct 13 at 14:00 CEST with Ramprasad Saptharishi: Reed-Solomon codes at capacity: a transparent proof of some recent breakthroughs

[Jakob Nordström]

Dear all,

With apologies for the somewhat short notice, we are happy to announce that on Tuesday October 13 at 14:00 CEST we will have the opportunity to listen to a seminar with Ramprasad Saptharishi from the Tata Institute of Fundamental Research Mumbai, who will give a talk titled "Reed-Solomon codes at capacity: a transparent proof of some recent breakthroughs". You find the abstract at the bottom of this message.

We will run this as a joint BARC/MIAO hybrid seminar at the University of Copenhagen. Local participants are warmly welcome to the Algorithms and Complexity Section at Vibenshuset, Lyngbyvej 2, while other participants are equally warmly welcome to join virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

More information about the MIAO seminar series can be found at https://jakobnordstrom.se/miao-seminars/ . If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

/Tuesday Oct 13 at 14:00 at the Algorithms and Complexity Section at the University of Copenhagen, Vibenshuset, Lyngbyvej 2, and on Zoom
*Reed-Solomon codes at capacity: a transparent proof of some recent breakthroughs
*(Ramprasad Saptharishi, Tata Institute of Fundamental Research Mumbai)
/
Recently, Brakensiek, Chen, Putterman, Zhang and Zheng proved a remarkable result that Reed-Solomon codes over large enough prime fields are list-decodable up to capacity, and admits an efficient list-decoding algorithm. This was shortly extended by Jeronimo to related questions of "proximity gaps" for these codes. Both of these theorems are remarkable achievements in the field of coding theory, but several technical aspects of the proofs were quite opaque and … artificial (ahem).

In this talk, I'll present a more transparent proof of the result. We'll first set up the general context of coding theory, the usual template of algebraic decoding algorithms, and see the complete proof of the BCPZZ result.

Depending on time, we can then also see the main ideas for the related question of proximity gaps.

Based on joint work with Prahladh Harsha and Mrinal Kumar (https://eccc.weizmann.ac.il/report/2026/232/).


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se