Pith. sign in

REVIEW 4 minor 37 references

Locality of Curve-Decoding and Improved Proximity Gaps

T0 review · 0 major / 4 minor · reviewed 2026-07-10 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Random codes match subspace-design codes for near-optimal proximity gaps by casting curve-decoding as a row-span constrained local property.

desk verdict Clean black-box fix that removes the exponential-ℓ loss for random ensembles and matches the subspace-design proximity-gap bound. read the letter →

arxiv 2607.08516 v1 pith:WHZ3WXDJ submitted 2026-07-09 cs.IT cs.CRmath.IT

Rohan Goyal , Venkatesan Guruswami , Yihang Sun , Mary Wootters This is my paper · ORCID
classification cs.ITcs.CRmath.IT MSC 94B0568Q2594B65
keywords proximitygapscurve-decodabilityrow-spanconstrainedLCLrandomlinearcodesReed-SolomonGallagerLDPCsubspacedesigncorrelatedagreement
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Proximity gaps let a verifier test whether every point on a low-degree curve is close to a code by sampling only a few points; they are central to interactive proofs and succinct arguments. Earlier work already gave near-optimal gaps (distance approaching the Singleton bound) for algebraic subspace-design codes, but the same parameters for random linear codes, random Reed-Solomon codes, and Gallager LDPC codes suffered an exponential blow-up in the degree. This paper removes that blow-up: with high probability the random ensembles achieve exactly the same quantitative bounds as the algebraic codes. The method is black-box transfer: any future improvement for subspace-design codes immediately upgrades the random ensembles. The technical step is to enlarge the existing local-property framework so that the global “no codeword curve through b nearby points” constraint can be encoded as a restriction on the row-span of a witness matrix; once curve-decodability itself becomes a local property, the known transfer theorems apply directly and the exponential loss disappears.

What carries the argument

Row-span constrained LCL properties: an r-local family of pairs (V,U) in which V supplies the usual coordinate-wise linear constraints while U further restricts the row-span of any witness matrix. Curve-decodability is shown to be exactly such a property, so the existing threshold theorems for random ensembles and for subspace-design codes transfer verbatim.

What would settle it

Exhibit a concrete subspace-design code (for example a folded Reed-Solomon code) whose curve-decodability radius is strictly worse than the bound claimed in the source theorem, or produce a random linear code of rate R that fails the stated proximity-gap condition for large ℓ.

Watch

Extended reading notes

Core claim

With high probability a random linear code, a random Reed-Solomon code, or a Gallager LDPC code of rate R exhibits (ℓ,1-R-2η,ε) proximity gaps (and the stronger correlated-agreement and mutual-correlated-agreement properties) whenever εq is at least nℓ(1-R)/η plus an additive O(ℓ²/η³) term, matching the best known bound for subspace-design codes and eliminating the previous (ℓ/η²)^O(ℓ) overhead.

Load-bearing premise

The argument treats as a black box the claim that every good subspace-design code is already curve-decodable with the near-optimal parameters; if that algebraic statement fails, the transfer to random ensembles collapses.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper improves proximity-gap (and stronger CA/MCA) parameters for three random ensembles—random linear codes, Reed–Solomon codes with random evaluation points, and Gallager LDPC codes—so that they match the near-optimal bounds previously obtained only for subspace-design codes. The key technical step is an extension of the LCL framework of LMS25/BCDZ25 to a row-span-constrained version (Section 3). With this machinery the authors cast non-curve-decodability exactly as membership in an explicit a-local family F (Theorem 4.4), prove that the associated threshold satisfies RF ≥ 1-δ-η (Corollaries 4.5–4.6), and then invoke the existing low-rate thresholds for the three ensembles (Corollaries 3.19, 3.21, 3.26) together with known list-decoding results. The final statements (Theorems 5.3, 5.6, 5.10) therefore replace the earlier (ℓ/η^{2})^O(ℓ) term by an additive O(ℓ^{2}/η^{3}) term, matching the subspace-design bound of GG25. The argument is advertised as a black-box transfer: any future improvement of curve-decodability for subspace-design codes automatically upgrades the random ensembles.

Significance. The quantitative improvement is load-bearing for applications that use large curve degree ℓ (e.g., WHIR, Blaze, Bolt). The black-box character of the transfer is a genuine methodological contribution: once curve-decodability is recognized as a row-span-constrained LCL property, every subsequent advance on subspace-design codes immediately yields the same advance for the three random ensembles. The re-derivation of the LCL threshold and transfer theorems in the constrained setting (Section 3) and the clean equivalence for Gallager codes (Appendix A) are carefully executed and should be reusable. The paper therefore both solves a concrete parameter gap left open by GG25 and supplies a reusable technical tool.

minor comments (4)
  1. In Definition 3.3 the phrase “row-span constrained r-local LCL family” is introduced; a short parenthetical reminder that the ordinary LCL notion of LMS25 is recovered by restricting U to L_dist would help readers who skip the introduction.
  2. Corollary 4.6 chooses the concrete constants a = ⌈100ℓ^{2}/η^{3}⌉ and b = ⌈4ℓ/η+ℓ⌉. A one-sentence remark that any sufficiently large absolute constants work (and that the 100 can be reduced) would make the dependence clearer.
  3. The factor-of-two loss in the list size for Gallager codes (Theorem 5.7 / Remark 5.8) is correctly flagged; it would be useful to state explicitly that the same loss already appears in the list-decoding transfer of MRRZ+21 and is not introduced by the new LCL machinery.
  4. A few typographical inconsistencies appear (e.g., “row-span constrained” vs. “row-constrained” in the introduction; occasional missing spaces after commas in displayed equations). A light copy-edit pass would remove them.

Circularity Check

1 steps flagged · score 2.0 of 10

Black-box transfer of curve-decodability parameters from authors' prior GG25; new LCL casting and thresholds are independent and non-circular.

  1. self citation load bearing [Section 1.2 (Putting it Together) and Corollary 4.5 / Theorem 2.15]
    "we know from [GG25] that subspace design codes satisfy curve-decodability; we have shown in Section 3 that random ensembles of codes behave similarly to subspace design codes for any row-span constrained LCL property; and we have shown in Section 4 that curve-decodability is such a property. Therefore random ensembles of codes exhibit good curve-decodability as well."

    The quantitative proximity-gap parameters for the random ensembles are obtained solely by transferring the concrete (a,b,δ) values that GG25 proved for subspace-design codes. GG25 shares two authors with the present paper; without that prior theorem the black-box transfer yields no numerical bound. The step is load-bearing for the main claim but is not definitional (the present paper does not redefine curve-decodability in terms of the random-code thresholds).

full rationale

The paper's derivation is a genuine black-box reduction: it proves that non-curve-decodability is exactly containment of a concrete row-span-constrained a-local family F (Theorem 4.4, with explicit |F| bound), obtains RF ≥ 1-δ-η from the subspace-design threshold machinery (Corollary 4.5 via the generalized Corollary 3.30), and then invokes the low-rate thresholds already established for RLC/RRS/RLDPC (Corollaries 3.19/3.21/3.26). The only external algebraic input that supplies the concrete parameters is GG25's Theorem 2.15 (curve-decodability of τ-subspace-design codes). That citation is load-bearing for the quantitative claim, and the author sets overlap, but the cited statement is an independent mathematical theorem proved in a separate paper; the present work never re-derives it from the target proximity-gap statement, nor defines any quantity in terms of the output parameters. No self-definitional loop, no fitted-input-as-prediction, no uniqueness theorem forbidding alternatives, and no ansatz smuggled via citation appear. The reductions from curve-decodability to CA/MCA/PG (Theorems 2.9–2.10) are likewise taken as black boxes from the same prior work. Score 2 reflects the single minor self-citation that is not definitionally circular.

Assumptions & free parameters 0 free parameters · 3 assumptions · 2 invented entities

The central claim rests on standard finite-field linear algebra, the known list-decoding capacity of random linear/RS/LDPC codes, the subspace-design curve-decodability theorem of GG25, and the ordinary LCL transfer theorems of LMS25/BCDZ25, all of which are external. The only new objects are the row-span constraint and the explicit family F that encodes curve-decodability; both are defined by pure linear-algebraic conditions with no free parameters.

assumptions (3)
  • domain assumption Every τ-subspace-design code is (ℓ,1-τ(d)-η,a,ηa/(d+η))-curve-decodable for d=⌈(ℓ+1)/η⌉ (GG25 Thm 4.7 / paper Thm 2.15).
    Load-bearing external algebraic fact; the entire black-box transfer inherits its parameters from this statement.
  • domain assumption Random linear codes (and, via transfer, random RS and sufficiently sparse Gallager LDPC) achieve list-decoding radius 1-R-3η/2 with list size O((1-R)/η) for large q (AGG+25).
    Used in Cor 2.11 to boost curve-decodability to CA/MCA; standard but non-trivial capacity result.
  • standard math Ordinary LCL threshold and transfer theorems of LMS25/BCDZ25 continue to hold after the row-span constraint is added (proved in §3).
    Re-derived rather than assumed; the proofs are self-contained linear-algebra counting arguments.
invented entities (2)
  • row-span constrained LCL family F ⊂ L(F^r_q)^n × L(F^r_q) independent evidence
    purpose: Allows global constraints (curve-freeness of the row-span) to be expressed inside the local-profile framework so that curve-decodability becomes an ordinary avoidance property.
    Defined purely by linear-algebraic conditions; no free parameters; independent evidence is the successful transfer of known thresholds.
  • (ℓ,A,b)-curve-free subspace independent evidence
    purpose: Encodes the global condition that no b columns of a witness matrix lie on a degree-ℓ codeword curve.
    Equivalent (Lemma 4.2) to a concrete restriction on the row-span; falsifiable by linear algebra.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Locality of Curve-Decoding and Improved Proximity Gaps." pith.science (2026). https://pith.science/paper/WHZ3WXDJ

@misc{pith2026260708516,
  author       = {Pith},
  title        = {Pith review of: Locality of Curve-Decoding and Improved Proximity Gaps},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WHZ3WXDJ}},
  note         = {Machine review of arXiv:2607.08516}
}
read the original abstract

Proximity gaps are a property of error correcting codes that arise in the study of Interactive Oracle Proofs (IOPs) and Succinct Non-interactive Arguments of Zero Knowledge (SNARKs). Recent work of Goyal and Guruswami has established near-optimal proximity gaps for many families of codes, including subspace design codes, as well as random ensembles like random linear codes, Reed-Solomon codes with random evaluation points, and Gallager's ensemble of LDPC codes (Goyal & Guruswami, 2025). However, the parameters for these latter randomized ensembles are worse than the parameters for subspace design codes, and degrade as the degree ell increases. In this work, we obtain improved proximity gaps for random ensembles of codes, including random linear codes, Reed-Solomon codes with random evaluation points, and Gallager's ensemble. Quantitatively, our results for these random ensembles match the results that Goyal and Guruswami attained for subspace design codes. In fact, our techniques are a black-box transference from subspace design codes: any progress on subspace design codes will automatically lead to analogous progress for these random ensembles. To obtain our results, we extend the Local Coordinate-wise Linear (LCL) property framework developed by Levi, Mosheiff, and Shagrithaya and by Brakensiek, Chen, Dhar, and Zhang to a \textit{row-span constrained} version (Levi, Mosheiff & Shagrithaya, 2025; Brakensiek, Chen, Dhar & Zhang, 2025). This allows us to cast \textit{curve-decodability} -- a property that implies proximity gaps -- directly as a row-span constrained LCL property, and make use of that machinery. In contrast, because curve-decodability is not obviously a vanilla LCL property, prior work had worked with a proxy property instead, leading to the aforementioned parameter losses.

Figures

Figures reproduced from arXiv: 2607.08516 by the authors.

Figure 1
Figure 1. Depiction of curve decodability (Definition 2.7). The orange stars represent f(α) ∈ C for α ∈ A, and the blue dots represent u(α) ∈ Σ n for α ∈ Fq, where u(x) is a degree-ℓ curve. Informally, a code C ⊆ Σ n is (ℓ, δ, a, b)-curve-decodable if the following holds: If there are at least a orange stars δ-close to distinct blue dots, then at least b of those orange stars lie on a degree-ℓ curve c(x). In the picture, a = … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages=

    Blaze: fast SNARKs from interleaved RAA codes , author=. Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages=. 2025 , organization=

    work page 2025

  2. [2]

    Low Density Parity Check Codes , year=

    Low-Density Parity-Check Codes , author=. Low Density Parity Check Codes , year=

    work page

  3. [3]

    Advances in Cryptology--EUROCRYPT 2025-44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2025, Proceedings , pages=

    WHIR: Reed-Solomon Proximity Testing with Super-Fast Verification , author=. Advances in Cryptology--EUROCRYPT 2025-44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2025, Proceedings , pages=. 2025 , organization=

    work page 2025

  4. [4]

    11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , pages=

    DEEP-FRI: Sampling Outside the Box Improves Soundness , author=. 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , pages=. 2020 , organization=

    work page 2020

  5. [5]

    33rd Computational Complexity Conference (CCC 2018) , pages=

    Worst-case to average case reductions for the distance to a code , author=. 33rd Computational Complexity Conference (CCC 2018) , pages=. 2018 , organization=

    work page 2018

  6. [6]

    Proceedings of the 2017 acm sigsac conference on computer and communications security , pages=

    Ligero: Lightweight sublinear arguments without a trusted setup , author=. Proceedings of the 2017 acm sigsac conference on computer and communications security , pages=

    work page 2017

  7. [7]

    Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages=

    Interactive proofs of proximity: delegating computation in sublinear time , author=. Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages=

    work page

  8. [8]

    Combinatorica , volume =

    Venkatesan Guruswami and Swastik Kopparty , title =. Combinatorica , volume =. 2016 , url =

    work page 2016

Show all 37 references
  1. [9]

    Cryptology ePrint Archive , year=

    Bolt: Faster SNARKs from Sketched Codes , author=. Cryptology ePrint Archive , year=

  2. [10]

    Cryptology ePrint Archive , year=

    Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes , author=. Cryptology ePrint Archive , year=

  3. [11]

    2026 , url =

    The Proximity Prize: Reed--Solomon Challenge , author =. 2026 , url =

    2026

  4. [12]

    2026 , url =

    Arnon, Gal and Boneh, Dan and Fenzi, Giacomo , title =. 2026 , url =

    2026

  5. [13]

    arXiv preprint arXiv:2512.08017 , year=

    Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes , author=. arXiv preprint arXiv:2512.08017 , year=

  6. [14]

    arXiv preprint arXiv:2510.13775 , year=

    Combinatorial Bounds for List Recovery via Discrete Brascamp--Lieb Inequalities , author=. arXiv preprint arXiv:2510.13775 , year=

  7. [15]

    arXiv preprint arXiv:2510.13777 , year=

    From random to explicit via subspace designs with applications to local properties and matroids , author=. arXiv preprint arXiv:2510.13777 , year=

  8. [16]

    2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Random Reed-Solomon codes and random linear codes are locally equivalent , author=. 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2025 , organization=

    2025

  9. [17]

    Journal of the ACM , volume=

    Proximity gaps for Reed--Solomon codes , author=. Journal of the ACM , volume=. 2023 , publisher=

    2023

  10. [18]

    2025 , url =

    Eli Ben-Sasson and Dan Carmon and Ulrich Haböck and Swastik Kopparty and Shubhangi Saraf , title =. 2025 , url =

    2025

  11. [19]

    Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

    Explicit folded reed-solomon and multiplicity codes achieve relaxed generalized singleton bounds , author=. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

  12. [20]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Improved list size for folded reed-solomon codes , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

    2025

  13. [21]

    Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Algorithmic improvements to list decoding of folded reed-solomon codes , author=. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , organization=

    2026

  14. [22]

    Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets , author=. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2014 , organization=

    2014

  15. [23]

    IEEE Transactions on Information Theory , volume=

    Tighter list-size bounds for list-decoding and recovery of folded Reed-Solomon and multiplicity codes , author=. IEEE Transactions on Information Theory , volume=. 2024 , publisher=

    2024

  16. [24]

    2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Improved decoding of folded Reed-Solomon and multiplicity codes , author=. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2018 , organization=

    2018

  17. [25]

    IEEE Transactions on Information Theory , volume=

    Linear-algebraic list decoding for variants of Reed--Solomon codes , author=. IEEE Transactions on Information Theory , volume=. 2013 , publisher=

    2013

  18. [26]

    IEEE Transactions on information theory , volume=

    Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy , author=. IEEE Transactions on information theory , volume=. 2008 , publisher=

    2008

  19. [27]

    IEEE Transactions on Information Theory , volume=

    Bounds for list-decoding and list-recovery of random linear codes , author=. IEEE Transactions on Information Theory , volume=. 2021 , publisher=

    2021

  20. [28]

    IEEE Transactions on Information Theory , volume=

    Threshold rates for properties of random codes , author=. IEEE Transactions on Information Theory , volume=. 2021 , publisher=

    2021

  21. [29]

    2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Punctured low-bias codes behave like random linear codes , author=. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2022 , organization=

    2022

  22. [30]

    Crites, Elizabeth and Stewart, Alistair , journal=. On

  23. [31]

    Cryptology ePrint Archive , year=

    On the distribution of the distances of random words , author=. Cryptology ePrint Archive , year=

  24. [32]

    arXiv preprint arXiv:2601.10047 , year=

    Optimal Proximity Gap for Folded Reed--Solomon Codes via Subspace Designs , author=. arXiv preprint arXiv:2601.10047 , year=

    arXiv

  25. [33]

    Advances in Combinatorics , year=

    Random Reed-Solomon codes achieve list-decoding capacity with linear-sized alphabets , author=. Advances in Combinatorics , year=

  26. [34]

    arXiv preprint arXiv:2604.15218 , year=

    Explicit Constant-Alphabet Subspace Design Codes , author=. arXiv preprint arXiv:2604.15218 , year=

    arXiv

  27. [35]

    2024 , url =

    Ulrich Haböck , title =. 2024 , url =

    2024

  28. [36]

    Low-Density Parity-Check Codes Achieve List-Decoding Capacity , volume=

    Mosheiff, Jonathan and Resch, Nicolas and Ron-Zewi, Noga and Silas, Shashwat and Wootters, Mary , year=. Low-Density Parity-Check Codes Achieve List-Decoding Capacity , volume=. SIAM Journal on Computing , publisher=. doi:10.1137/20m1365934 , number=

    doi

  29. [37]

    2026 , url =

    Dmitry Krachun and Stepan Kazanin and Ulrich Haböck , title =. 2026 , url =

    2026

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.