For Reed–Solomon codes over prime fields, proximity gaps — in their strongest correlated-agreement form — are proven up to the Johnson radius and known to fail at radii within Θ(1/log⁡n)\Theta(1/\log n) of the capacity radius 1−ρ1-\rho for multiplicative-subgroup domains. The open problem asks for the behavior in the remaining regime: in particular, whether every Reed–Solomon code over a prime field is list-decodable up to the Elias radius with list sizes ℓ(θ)≤c1⋅2c2H(ρ)/η\ell(\theta)\le c_1\cdot 2^{c_2 H(\rho)/\eta} at distance θ=1−ρ−η\theta=1-\rho-\eta (S-two Conjecture 1) and line-decodable at the same distances with threshold a=ℓ(θ)⋅n+o(n)a=\ell(\theta)\cdot n+o(n) (S-two Conjecture 2); the behavior of the correlated-agreement error between the Johnson radius and capacity is related context, not a separate deliverable. The question underpins the soundness analysis of FRI/STARK-type proof systems and is the subject of the Ethereum Foundation's $1M Proximity Prize.

Background

A Reed–Solomon code C=RS[F,D,k]C=\mathrm{RS}[\mathbb{F},D,k] is the set of evaluations on a domain D⊆FD\subseteq\mathbb{F}, ∣D∣=n|D|=n, of all polynomials of degree at most kk; its rate is ρ=k/n\rho=k/n and, being maximum distance separable, its relative minimum distance is 1−ρ1-\rho. For a word uu and code CC, Δ(u,C)\Delta(u,C) denotes the relative Hamming distance to the closest codeword. A code is list-decodable at radius θ\theta with list size ℓ\ell if every word uu has at most ℓ\ell codewords within relative distance θ\theta. The Johnson radius 1−ρ1-\sqrt{\rho} is the largest radius up to which every code of rate ρ\rho has polynomial list sizes, and the Guruswami–Sudan algorithm list-decodes Reed–Solomon codes up to it; whether Reed–Solomon codes are well list-decodable beyond the Johnson radius is a long-standing open problem. The information-theoretic ceiling is the Elias radius rE(ρ)r_E(\rho), defined by ρ=1−H∣F∣(rE)\rho=1-H_{|\mathbb{F}|}(r_E) where HqH_q denotes the qq-ary entropy function (the binary entropy H=H2H=H_2 enters separately, in the conjectured list-size exponent): beyond it the volume of Hamming balls forces superpolynomial lists for every code, so rE(ρ)r_E(\rho) is also called the list-decoding capacity bound, and it satisfies 1−ρ−1/log⁡2∣F∣≤rE(ρ)<1−ρ1-\rho-1/\log_2|\mathbb{F}|\le r_E(\rho)<1-\rho.

Proximity gaps and correlated agreement refine list-decodability in a way that is central to the soundness analysis of hash-based succinct arguments (SNARKs), notably the FRI low-degree test underlying STARK proof systems. An F\mathbb{F}-linear code CC has a proximity gap at distance θ\theta with threshold aa if whenever more than aa points on an affine line {f+zg:z∈F}⊆FD\{f+zg:z\in\mathbb{F}\}\subseteq\mathbb{F}^D are θ\theta-close to CC, the whole line is θ\theta-close to CC; the strongest form is correlated agreement: then the pair [f,g][f,g] is itself θ\theta-close to the interleaved code C2C^2 (the code of pairs of codewords evaluated coordinatewise), meaning ff and gg agree with codewords of CC on one common set of ≥(1−θ)n\ge(1-\theta)n coordinates. The threshold aa translates directly into the field size, and hence proof size, needed for a target soundness error a/∣F∣a/|\mathbb{F}|. A weaker quantitative target is the correlated-agreement error εca(C,θ)\varepsilon_{\mathrm{ca}}(C,\theta), the fraction of z∈Fz\in\mathbb{F} that can be θ\theta-close to CC while [f,g][f,g] is not. Line-decodability is the corresponding threshold property for lines, and curve-decodability its extension to degree-MM curves ∑izifi\sum_i z^i f_i.

Ben-Sasson, Carmon, Ishai, Kopparty and Saraf introduced proximity gaps for Reed–Solomon codes and proved them up to the Johnson radius; their Conjecture 8.4 (ePrint 2020/654) asserted correlated agreement all the way up to capacity, i.e. at every distance θ≤1−ρ−η\theta\le 1-\rho-\eta with error poly(n)/∣F∣\mathrm{poly}(n)/|\mathbb{F}|. This up-to-capacity picture has since been dismantled from above: Crites and Stewart disproved the up-to-capacity correlated-agreement, mutual-correlated-agreement and list-decodability conjectures (beyond the Elias radius, where list sizes must grow exponentially in nn) and proposed modified conjectures up to the Elias radius, and Ben-Sasson, Carmon, Haböck, Kopparty and Saraf refuted the nτn^\tau-bounded proximity-gap conjectures at constant distance. Most recently, Krachun, Kazanin and Haböck, and independently Kambiré, who gives an explicit quantitative Linnik-type bound on the prime, constructed over multiplicative-subgroup domains of prime fields — exactly the smooth domains used in practical FRI instantiations — affine lines with nτn^\tau many points θ\theta-close to the code at θ=1−ρ−Θ(1/log⁡n)\theta=1-\rho-\Theta(1/\log n), together with words having polynomially large lists at the same distances, while correlated agreement fails. So proximity gaps with polynomial threshold, and list sizes polynomial in 1/η1/\eta, are impossible even below the Elias radius for these structured domains.

On the positive side, Goyal and Guruswami proved that subspace-design codes (folded Reed–Solomon and multiplicity codes) and Reed–Solomon codes with randomly chosen evaluation domains do enjoy proximity gaps and correlated agreement up to (near) capacity with essentially optimal thresholds — so the obstruction is specific to prescribed, structured domains. A companion notion, mutual correlated agreement, is the variant used in the analysis of protocols such as WHIR. What remains open is the regime between the Johnson radius and the counterexample zone: the sharpest current formulation of the surviving question is due to the S-two whitepaper (Carmon, Goldberg, Haböck, Lerer, Lesokhin, Papini, Samocha), whose Appendix A.5 uses the Krachun–Kazanin construction to calibrate two conjectures that are consistent with all known counterexamples and are relied upon, unproven, for the concrete security parameters of the S-two proof system. The Ethereum Foundation has announced a $1M Proximity Prize for resolving exactly this band.

Problem Statement

Determine the proximity-gap and list-decoding behavior of Reed–Solomon codes over prime fields at radii between the Johnson radius and the capacity radius 1−ρ1-\rho. The concrete target is the pair of conjectures stated in Appendix A.5 of the S-two whitepaper, which together assert that Reed–Solomon codes over prime fields are decodable up to the information-theoretic (Elias) limit with near-random-code parameters:

(1) List-decodability up to list-capacity: is it true that for every rate ρ∈(0,1)\rho\in(0,1) there exist constants c1,c2≥1c_1,c_2\ge 1 such that every Reed–Solomon code RS[Fp,D,k]\mathrm{RS}[\mathbb{F}_p,D,k] over a prime field with rate ρ\rho is combinatorially list-decodable at every distance θ=1−ρ−η\theta=1-\rho-\eta up to the Elias radius rE(ρ)r_E(\rho), with list size ℓ(θ)≤c1⋅2c2H(ρ)/η\ell(\theta)\le c_1\cdot 2^{c_2 H(\rho)/\eta}, where HH is the binary entropy function?

(2) Line-decodability up to list-capacity: is the same code family line-decodable at the same distances, in the sense that whenever more than a=ℓ(θ)⋅n+o(n)a=\ell(\theta)\cdot n+o(n) points of an affine line {f+zg}\{f+zg\} are θ\theta-close to the code, the pair [f,g][f,g] is θ\theta-close to the interleaved code C2C^2 (correlated agreement at distance θ\theta), with ℓ(θ)\ell(\theta) as in (1)? The whitepaper states the conjecture for domains in a prime field and notes it extends to alphabet extension fields.

These two conjectures form one objective — establishing the correct decoding geometry of Reed–Solomon codes over prime fields near the information-theoretic limit — because the conjectured line-decodability threshold is expressed directly through the conjectured list sizes (and known bootstrap arguments show list sizes essentially determine the threshold). The list-size bound of (1) already yields the line-decodability threshold of (2) through these bootstrap arguments. As related, non-prescriptive context: the Arnon–Boneh–Fenzi survey (ePrint 2026/680), companion to the Ethereum Foundation's 1MProximityPrize,formalizesgrandchallengesasking,forReed–Solomoncodeswithprescribed(inparticularsmoothmultiplicative−subgroup)domainsandratesin1M Proximity Prize, formalizes grand challenges asking, for Reed–Solomon codes with prescribed (in particular smooth multiplicative-subgroup) domains and rates in {1/2,1/4,1/8,1/16},todeterminethelargestproximityradius, to determine the largest proximity radius \delta^*_Catwhichthemutual−correlated−agreementerrorstaysatmostat which the mutual-correlated-agreement error stays at most2^{-128}$ and the corresponding interleaved list size stays negligible; these numerical threshold challenges are distinct from the universal asymptotic conjectures (1)–(2) and are not part of the resolution criterion.

References

  1. Antonio Kambiré. “Proximity Gaps Conjecture Fails Near Capacity over Prime Fields.” arXiv:2604.09724, DOI 10.48550/arXiv.2604.09724, 2026. https://arxiv.org/abs/2604.09724
  2. Dmitry Krachun, Stepan Kazanin, and Ulrich Haböck. “Failure of proximity gaps close to capacity.” IACR Cryptology ePrint Archive, Paper 2026/782, 2026. https://eprint.iacr.org/2026/782
  3. Dan Carmon, Lior Goldberg, Ulrich Haböck, Leonardo Lerer, Ilya Lesokhin, Shahar Papini, and Shahar Samocha. “S-two Whitepaper.” IACR Cryptology ePrint Archive, Paper 2026/532, 2026. https://eprint.iacr.org/2026/532
  4. Eli Ben-Sasson, Dan Carmon, Ulrich Haböck, Swastik Kopparty, and Shubhangi Saraf. “On Proximity Gaps for Reed–Solomon Codes.” Electronic Colloquium on Computational Complexity, Report TR25-169, 2025. https://eccc.weizmann.ac.il/report/2025/169/
  5. Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. “Proximity Gaps for Reed–Solomon Codes.” IACR Cryptology ePrint Archive, Paper 2020/654, 2020. https://eprint.iacr.org/2020/654
  6. Elizabeth Crites and Alistair Stewart. “On Reed–Solomon Proximity Gaps Conjectures.” IACR Cryptology ePrint Archive, Paper 2025/2046, 2025. https://eprint.iacr.org/2025/2046
  7. Rohan Goyal and Venkatesan Guruswami. “Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed–Solomon Codes.” IACR Cryptology ePrint Archive, Paper 2025/2054, 2025. https://eprint.iacr.org/2025/2054
  8. Gal Arnon, Dan Boneh, and Giacomo Fenzi. “Open Problems in List Decoding and Correlated Agreement.” IACR Cryptology ePrint Archive, Paper 2026/680, 2026. https://eprint.iacr.org/2026/680
  9. Rohan Goyal, Venkatesan Guruswami, Yihang Sun, and Mary Wootters. “Locality of Curve-Decoding and Improved Proximity Gaps.” arXiv:2607.08516, 2026. https://arxiv.org/abs/2607.08516
  10. Sunghyeon Jo. “Reed–Solomon Mutual Correlated Agreement Beyond the Johnson Radius.” IACR Cryptology ePrint Archive, Paper 2026/1432, 2026. https://eprint.iacr.org/2026/1432
  11. Ethereum Foundation. “The Proximity Prize — $1M Reed–Solomon Challenge.” 2026. https://proximityprize.org/