--- id: "2026-09-04-reed-solomon-list-decoding-capacity-ai" url: "https://postcutoff.com/e/2026-09-04-reed-solomon-list-decoding-capacity-ai/" as_of: "2026-11-22T13:32:00+01:00" date: "2026-09-04" date_precision: day category: science importance: 4 confidence: medium status: [Awaiting review] verification: Expert-checked sources: 8 editor: human editor human_review: null version: "2026-10-29" --- As of: 2026-11-22 13:32 CET. Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/ Canonical page: https://postcutoff.com/e/2026-09-04-reed-solomon-list-decoding-capacity-ai/ # Reed–Solomon codes list-decoded up to capacity and proximity gaps settled, with GPT-5.6 Sol and ChatGPT 5.6 Pro (Brakensiek–Chen–Putterman–Zhang–Zheng; Jeronimo) In early September 2026 two preprints settled long-standing problems about Reed–Solomon codes, the most widely used error-correcting codes. Brakensiek, Chen, Putterman, Zhang and Zheng (ECCC TR26-164, 4 Sept; arXiv 2609.08005) gave a deterministic polynomial-time algorithm that list-decodes RS codes over prime fields up to capacity, far past the Guruswami–Sudan/Johnson barrier. Jeronimo (arXiv 2609.05870, 5 Sept) extended it to all rates and proved near-optimal proximity gaps (mutual correlated agreement), the property behind the Ethereum Foundation's $1M Proximity Prize. Both disclose substantial AI help: GPT-5.6 Sol "to help produce the rest of the results" and ChatGPT 5.6 Pro interactions "crucial". ## Key facts - Brakensiek, Chen, Putterman, Zhang, Zheng, 'Algorithmic List Decoding of Reed–Solomon Codes up to Capacity': ECCC TR26-164 (4 Sept 2026), arXiv 2609.08005 (7 Sept). Deterministic poly-time decoding over prime fields from a 1−R−δ fraction of errors, every evaluation set; first for low constant rate, extended to all constant rates with a padding reduction from Alrabiah, Goyal and Guruswami - Their AI statement: inspired by a Proximity Prize submission on better.codes by user 'nasqret' that went slightly beyond the Johnson radius for one rate-1/2 code of length 2^18; the authors 'relied on AI interaction, specifically GPT-5.6 Sol, to help produce the rest of the results of this paper'; all statements 'independently verified by the authors' - They also note that after their posting 'a number of groups contemporaneously realized (with LLM assistance)' how to extend the proof white-box to all rates - Jeronimo, 'Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed–Solomon Codes': arXiv 2609.05870 (5 Sept), ECCC TR26-169. List decoding at capacity for every rate with list size n^{O(1)} independent of q, plus mutual correlated agreement (MCA) with error n^{O(1)}/q and no proximity loss; it gives fixed-slack certificates for the MCA and list-size targets of the preliminary Proximity Prize statement, but 'does not determine their largest safe radius' - Jeronimo's AI disclosure: 'The interactions with ChatGPT 5.6 Pro were crucial in obtaining the main results of this paper.' - Proximity Prize: a $1,000,000 Ethereum Foundation programme on RS proximity gaps and list decoding (judges Dan Boneh, Giacomo Fenzi, Gal Arnon; deadline 31 Dec 2027; 'AI-aided submissions are allowed'); companion live Lean-scored challenge at better.codes. No award announced as of 7 Oct 2026 - Follow-ups: Dao, Kominers and Thaler (IACR ePrint 2026/2056, 16 Sept) give quantitative versions over cryptographic fields and report proof-size savings of 4.6–11.1% in ProveKit, ZisK and LambdaVM; Harsha, Kumar and Saptharishi (TIFR) posted a unified exposition (arXiv 2610.08610, 6 Oct) saying both problems 'were resolved in the last few weeks with AI assistance' and that they used Claude (Opus and Sonnet) to understand the dense originals - Verification status: unrefereed preprints, but already re-derived independently in an expository paper by three coding theorists - Follow-up (28 Oct): Omar Alrabiah, Rohan Goyal and Venkatesan Guruswami (arXiv 2610.36215) give explicit Reed–Solomon codes over extension fields of size poly(n) that are list-decodable from a 1−R−ε fraction of errors with the optimal list size O((1−R)/ε), deterministic decoding, line decoding and proximity gaps. AI disclosure: 'Our key results, and the paper writing were substantially aided by the use of ChatGPT 5.6 Sol and ChatGPT 6 Astra'; GPT-5.6 Sol 'found one of the central ideas in the paper', a small family of automorphisms generating the Galois group in place of Guruswami–Xing's subfield-evaluation and Frobenius method ## What happened Reed–Solomon (RS) codes encode a message as the values of a low-degree polynomial. They are used in storage, communications and, more and more, in the hash-based proof systems (STARKs, FRI and relatives) behind blockchain scaling. Two questions about them had been open for decades. One was whether RS codes can be decoded efficiently from errors beyond the Johnson radius, the limit of the Guruswami–Sudan algorithm (1999), all the way up to the information-theoretic capacity. The other was whether RS codes have "proximity gaps" up to capacity: if many points on a line of words are close to the code, all of them are, with correlated agreement. The second property sets the soundness and therefore the proof size of FRI-style proof systems. In 2025 the Ethereum Foundation put up a $1M **Proximity Prize** for it, with a live companion challenge at better.codes. On 4 September 2026, Joshua Brakensiek, Yeyuan Chen, Aaron Putterman, Zihan Zhang and Kai Zhe Zheng posted a deterministic polynomial-time algorithm that list-decodes RS codes over prime fields up to capacity for low constant rates (ECCC TR26-164; arXiv 2609.08005). Within days a revision extended it to all constant rates, using a padding observation from Alrabiah, Goyal and Guruswami. On 5 September Fernando Granha Jeronimo posted a unified "hidden-derivative" framework (arXiv 2609.05870). It gives capacity list decoding with list size independent of the field and near-optimal mutual correlated agreement, which certifies the asymptotic targets of the prize statement but not the largest safe radius. Both papers credit AI heavily. Brakensiek et al. say they started from a better.codes submission by the user "nasqret", which pushed one specific code slightly past the Johnson radius. They "relied on AI interaction, specifically GPT-5.6 Sol, to help produce the rest of the results of this paper". They also note that several groups "contemporaneously realized (with LLM assistance)" how to extend the proof to all rates. Jeronimo writes that "the interactions with ChatGPT 5.6 Pro were crucial in obtaining the main results". Follow-ups came quickly. Dao, Kominers and Thaler (a16z crypto) made the bounds quantitative over cryptographic fields and reported 4.6–11.1% smaller proofs in existing systems (IACR ePrint 2026/2056). On 6 October, Prahladh Harsha, Mrinal Kumar and Ramprasad Saptharishi (TIFR) posted a unified exposition (arXiv 2610.08610). They write that the problems "have recently met their fate, thanks to some heavy lifting by AI tools" and that understanding the dense originals took "several extended conversations with Claude (Opus and Sonnet)". The exposition itself is human-written. The Proximity Prize page lists no award as of 7 October 2026. Its rules allow AI-aided submissions if they are human-verified. ## Why it matters This is one of the clearest cases so far of AI-assisted research changing a central result in theoretical computer science with direct engineering consequences: proximity-gap bounds feed straight into the parameters and proof sizes of deployed zero-knowledge systems. It also shows a new research pipeline: a crypto bounty, a crowd-sourced Lean-scored leaderboard, an anonymous submission and chatbot-assisted generalisation, all within weeks. Earlier update runs did not catch it (the papers sit on ECCC and in cs.IT, not in the maths listings the sweep scans); the TIFR exposition's AI note surfaced it a month later. ## What is disputed or not yet verified - Verification: Unrefereed preprints (ECCC/arXiv); independent expository re-proof by Harsha–Kumar–Saptharishi (arXiv 2610.08610) ## Your AI and this story - GPT-6.2 Astra (training cutoff May 2026): 96 days after its cutoff - Claude Opus 5.5 (training cutoff June 2026): 66 days after its cutoff - Gemini 4 Hydrogen (training cutoff March 2026): 157 days after its cutoff - Grok 4.7 (training cutoff May 2026): 96 days after its cutoff ## Sources 1. [ECCC TR26-164: Algorithmic List Decoding of Reed–Solomon Codes up to Capacity](https://eccc.weizmann.ac.il/report/2026/164/) (eccc.weizmann.ac.il, paper) 2. [arXiv 2609.08005 (Brakensiek, Chen, Putterman, Zhang, Zheng)](https://arxiv.org/abs/2609.08005) (arxiv.org, paper) 3. [arXiv 2609.05870: Jeronimo, list decoding at capacity and optimal proximity gaps](https://arxiv.org/abs/2609.05870) (arxiv.org, paper) 4. [ECCC TR26-169 (Jeronimo)](https://eccc.weizmann.ac.il/report/2026/169/) (eccc.weizmann.ac.il, paper) 5. [arXiv 2610.08610: Harsha, Kumar, Saptharishi, Reed–Solomon codes at capacity (exposition)](https://arxiv.org/abs/2610.08610) (arxiv.org, paper) 6. [IACR ePrint 2026/2056: Dao, Kominers, Thaler, Reed–Solomon codes beyond Johnson](https://eprint.iacr.org/2026/2056) (eprint.iacr.org, paper) 7. [Ethereum Foundation: The Proximity Prize](https://proximityprize.org/) (proximityprize.org, official) 8. [Alrabiah, Goyal, Guruswami, arXiv 2610.36215: Explicit Reed–Solomon subspace designs: optimal list and line decoding](https://arxiv.org/abs/2610.36215) (arxiv.org, paper) ## Changes - 2026-10-29: Added the Alrabiah–Goyal–Guruswami explicit construction with optimal list size and its AI disclosure (science agent, PDF scan) - 2026-10-13: Related: added [October 2026: the arXiv stream of conjectures settled with disclosed AI help continues](https://postcutoff.com/e/2026-10-13-ai-assisted-results-october-2026/) (October catalogue, split out of the summer catalogue) - 2026-10-07: Science block: short label for the open-problems table - 2026-10-07 (filed): Created from the TIFR exposition (arXiv 2610.08610); AI statements read in both original PDFs ## Related - 2026-10-29: [AI-assisted results in the 29 Oct 2026 sweep](https://postcutoff.com/e/2026-10-29-ai-assisted-results-october-29-listing/index.md) - 2026-10-13: [October 2026: the arXiv stream of conjectures settled with disclosed AI help continues](https://postcutoff.com/e/2026-10-13-ai-assisted-results-october-2026/index.md) - 2026-09-30: [Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help](https://postcutoff.com/e/2026-09-30-ai-assisted-conjecture-wave-summer-2026/index.md) - 2026-07-09: [OpenAI broadly releases GPT-5.6 after government-gated preview](https://postcutoff.com/e/2026-07-09-gpt-5-6-sol-terra-luna/index.md)