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)

2026-09-04★★★★after cutoffscienceSimons InstituteOpenAIEthereum Foundationconfidence: medium

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

Science result

Field: computer-science / coding theory / pseudorandomness / cryptographic proof systems
Problem: Efficient list decoding of Reed–Solomon codes beyond the Johnson radius up to capacity; proximity gaps / mutual correlated agreement for RS codes (open since 1999)
Result: Deterministic polynomial-time list decoding of RS codes over prime fields up to capacity for every constant rate and evaluation set, and near-optimal mutual correlated agreement (proximity gaps) up to capacity with fixed slack.
AI system: GPT-5.6 Sol, ChatGPT 5.6 Pro, ChatGPT 6 Pro
Human role: AI-assisted: humans extracted the idea from a crowd-sourced prize submission and directed the work; GPT-5.6 Sol helped produce most of the remaining results (BCPZZ); ChatGPT 5.6 Pro interactions were 'crucial' (Jeronimo); authors verified everything
Verification: Unrefereed preprints (ECCC/arXiv); independent expository re-proof by Harsha–Kumar–Saptharishi (arXiv 2610.08610)
Status: pending
Why surprising: The Guruswami–Sudan decoder's Johnson-radius barrier had stood since 1999; it fell within weeks of a crypto prize launch, with frontier chatbots credited for much of the work.

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.

Changelog

2026-10-07: created from the TIFR exposition (arXiv 2610.08610) found in sweep 2026-10-07; AI statements read in both original PDFs

Related events

2026-09-30Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help (July–September catalogue) ★★★★
2026-07-09OpenAI broadly releases GPT-5.6 (Sol, Terra, Luna) after government-gated preview ★★★★

Sources (7)

id: 2026-09-04-reed-solomon-list-decoding-capacity-ai · updated 2026-10-07 · open in the interactive timeline