Reed-Solomon List Decoding Breakthrough Resolves Major Open Problem in Coding Theory
AlexKontorovich · x · 2026-09-04
A long-standing open problem in coding theory has been resolved: whether explicit Reed-Solomon codes can be list decoded beyond the Guruswami-Sudan breakthrough. A team of Joshua Brakensiek, Yeyuan Chen, Louie Putterman, Zihan Zhang, and Kai Zhe Zheng published ECCC report TR26-164, presenting a deterministic polynomial-time list decoding algorithm for Reed-Solomon codes over prime fields that approaches list decoding capacity on every evaluation set in the low (constant) rate regime.
More from Research
- Synthesizing CoT training data with a FIM model to train 2B/9B reasoning GANs — cephaloform · 2026-09-04
- Speculation: OpenAI may internalize reasoning via synthetic CoT rewriting and FiM — cephaloform · 2026-09-04
- Autoregression explained: a language model is just a next-token guesser in a loop — sethjuarez · 2026-09-04
- Geoffrey Irving: Conceptual Alignment Research Can Still Win on Short Timelines — geoffreyirving · 2026-09-04
- New study tests whether multilingual LLMs process cross-linguistic syntactic structures with shared mechanisms — EliasEskin · 2026-09-04
- Running Boltz-2 100 Million Times: Toward a Bottom-Up Path to Virtual Cells — HannesStaerk · 2026-09-04