arxiv: 2605.07595 · v1 · submitted 2026-05-08 · 💻 cs.IT · math.IT

Recognition: no theorem link

A Syndrome-Space Approach to Proximity Gaps and Correlated Agreement for Random Linear Codes

Chen Yuan, Ruiqi Zhu

Pith reviewed 2026-05-11 02:28 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords proximity gapscorrelated agreementrandom linear codessyndrome spaceparity-check matrixIOPPSNARKlist decoding

0 comments

The pith

Random linear codes admit direct proximity gap proofs up to near-capacity radii via syndrome-space reformulation.

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

The paper develops a direct method to establish proximity gaps and correlated agreement statements for random linear codes. It works in the random parity-check-matrix model by reformulating questions in syndrome space and applying a witness-based reduction to structured sets such as lines, affine spaces, and polynomial curves. This avoids list decoding as the central tool and produces sharper radius bounds than prior approaches. The results matter because proximity gaps let verifiers draw global soundness conclusions from a few random queries in sampling-based proof systems. If the statements hold, random linear codes can support interactive oracle proofs of proximity and code-based SNARKs with tighter parameters.

Core claim

We establish a direct approach to proximity gaps and correlated agreement for random linear codes in the random parity-check-matrix model, without relying on list decoding as the main engine of the proof. Our approach is based on a syndrome-space reformulation together with a witness-based reduction mechanism, and it yields strong results for affine lines, affine spaces, and polynomial curves. It leads to the optimal-up-to-ε large-alphabet radius bound ρ<1-R-ε for q=Θ(n), as well as near-capacity bounds over constant alphabets with improved alphabet-size requirements.

What carries the argument

Syndrome-space reformulation paired with a witness-based reduction that maps structured sets while preserving distance properties.

If this is right

Proximity gaps hold for affine lines, spaces, and curves up to radius 1-R-ε when the alphabet size is linear in block length.
Near-capacity radius bounds become available for constant alphabets with smaller alphabet-size requirements than earlier methods.
Random linear codes can serve as the underlying object in IOPPs and code-based SNARKs without an intermediate list-decoding step.
Sampling-based soundness arguments gain direct support from the syndrome-space view rather than decoding surrogates.
Correlated agreement statements follow for the same structured sets under the same radius bounds.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The technique may extend to other families of linear codes whose parity-check matrices behave like random ones under mild assumptions.
Tighter parameters could reduce the number of queries needed in practical SNARK constructions that rely on proximity testing.
The reformulation might connect to other coding-theoretic questions such as list-decodability thresholds or average-case hardness results.
If the witness reduction generalizes, similar direct proofs could apply to additional structured objects like higher-degree varieties.

Load-bearing premise

The random parity-check-matrix model accurately reflects the distance behavior of the random linear codes, and the witness-based reduction keeps the required proximity properties intact for the structured point sets.

What would settle it

A small explicit random linear code together with an affine line or curve containing a non-negligible fraction of points at distance exactly 1-R-ε from the code while the rest lie far away would contradict the claimed gap.

read the original abstract

Proximity gaps and correlated agreement have become central tools in the analysis of interactive oracle proofs of proximity (IOPPs) and code-based SNARKs. Informally, a proximity-gap statement says that for a structured set of words -- such as a line, an affine space, or a curve -- either all points are close to the code, or most are far from it. Such statements are essential in sampling-based proof systems, where a verifier queries only a few random locations on a structured object but must still obtain a global soundness guarantee. In Reed--Solomon-based proof systems, one would ideally like the proximity parameter to approach the information-theoretic limit $1-R$, since this is the largest possible radius for a rate-$R$ code and directly affects protocol efficiency. While recent work has substantially strengthened the picture for algebraic codes and linked proximity gaps to decoding-related structural properties, it remains unclear whether analogous results for random linear codes can be proved directly, rather than through decoding-theoretic surrogates. In this work, we establish a direct approach to proximity gaps and correlated agreement for random linear codes in the random parity-check-matrix model, without relying on list decoding as the main engine of the proof. Our approach is based on a syndrome-space reformulation together with a witness-based reduction mechanism, and it yields strong results for affine lines, affine spaces, and polynomial curves. It is conceptually different from the existing decoding-driven route for random linear codes, and it also leads to sharper parameters, including the optimal-up-to-$\varepsilon$ large-alphabet radius bound $\rho<1-R-\varepsilon$ for $q=\Theta(n)$, as well as near-capacity bounds over constant alphabets with improved alphabet-size requirements.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives a direct syndrome-space proof for proximity gaps on random linear codes that skips list decoding and tightens the radius bounds.

read the letter

The main takeaway is that the authors replace the usual list-decoding route with a syndrome-space reformulation and a witness-based reduction. This works directly in the random parity-check-matrix model and produces proximity-gap statements for lines, affine spaces, and curves. The payoff is the stated radius improvement: ρ < 1-R-ε when the alphabet is linear in n, plus near-capacity results for constant alphabets with weaker alphabet-size demands than earlier work. That is the concrete advance over prior decoding-driven arguments for the same codes. The approach looks cleaner because it stays inside the syndrome view and uses the model's probabilistic distance properties to bound the error terms in the reduction. No obvious circularity or self-referential fitting appears in the argument structure. The distinction from list-decoding surrogates is drawn clearly, which helps readers see what is actually new. One soft spot is the dependence on the random parity-check model itself. If applications need codes outside that ensemble, the results may not transfer without extra work. A second minor point is that the paper would benefit from a short table comparing the new parameters side-by-side with the best previous bounds so the improvement is quantified rather than asserted. The central claims seem to hold up on their own terms. This is useful reading for people who design IOPPs or code-based SNARKs and want to push soundness closer to capacity without algebraic structure. A referee can check the reduction steps and the probabilistic estimates directly, so the paper deserves peer review.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces a syndrome-space reformulation together with a witness-based reduction to prove proximity-gap and correlated-agreement statements directly for random linear codes in the random parity-check-matrix model. The approach is explicitly distinguished from list-decoding arguments and is applied to affine lines, affine spaces, and polynomial curves, yielding the radius bound ρ < 1−R−ε for q = Θ(n) as well as near-capacity bounds for constant alphabets with improved alphabet-size requirements.

Significance. If the central claims hold, the work supplies a conceptually new, direct route to proximity gaps for random linear codes that avoids decoding-theoretic intermediaries and improves parameter regimes relevant to IOPPs and code-based SNARKs. The probabilistic control of error terms via the random parity-check model and the explicit witness-based reduction constitute clear strengths; the paper does not claim machine-checked proofs or reproducible code but the directness of the argument is a positive feature.

minor comments (2)

[Abstract] Abstract: the phrase 'witness-based reduction mechanism' is introduced without a one-sentence indication of how the witness is constructed or how it preserves the required distance properties for lines/spaces/curves; adding this would improve readability for readers outside the immediate sub-area.
[Main theorems (likely §3–4)] The random parity-check-matrix model is invoked to control reduction error terms, but the precise probability space (e.g., whether entries are chosen uniformly or with any sparsity constraint) is not restated in the statement of the main theorems; a brief reminder in §3 or §4 would eliminate ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and insightful review, which accurately captures the core contribution of our manuscript: a direct syndrome-space approach to proximity gaps and correlated agreement for random linear codes that avoids list-decoding intermediaries. The referee's recognition of the conceptual novelty, the witness-based reduction, and the improved parameter regimes (including the near-optimal radius for large alphabets) is appreciated. We will make the minor revisions needed to improve clarity and presentation.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents a direct syndrome-space reformulation combined with a witness-based reduction to establish proximity-gap and correlated-agreement statements for random linear codes under the random parity-check-matrix model. This route is explicitly separated from list-decoding arguments and derives the stated radius bounds (ρ < 1-R-ε for large alphabets and near-capacity results for constant alphabets) from the model's probabilistic distance properties. No load-bearing step reduces by construction to a fitted parameter, self-citation chain, or renamed input; the derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only; no explicit free parameters, axioms, or invented entities are stated. The random parity-check-matrix model is invoked as the setting but not derived.

axioms (1)

domain assumption Random parity-check-matrix model for linear codes
The entire development is stated to hold in this model; no justification or alternative model is discussed in the abstract.

pith-pipeline@v0.9.0 · 5610 in / 1158 out tokens · 26242 ms · 2026-05-11T02:28:03.105364+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

[1]

Cryptology ePrint Archive , year=

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

work page
[2]

Advances in Combinatorics , year=

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

work page
[3]

Journal of the ACM , volume=

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

work page 2023
[4]

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

WHIR: Reed--Solomon proximity testing with super-fast verification , author=. Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages=. 2025 , organization=

work page 2025
[5]

45th international colloquium on automata, languages, and programming (icalp 2018) , pages=

Fast reed-solomon interactive oracle proofs of proximity , author=. 45th international colloquium on automata, languages, and programming (icalp 2018) , pages=. 2018 , organization=

work page 2018
[6]

arXiv preprint arXiv:1903.12243 , year=

DEEP-FRI: sampling outside the box improves soundness , author=. arXiv preprint arXiv:1903.12243 , year=

work page arXiv 1903
[7]

Annual International Cryptology Conference , pages=

STIR: reed-solomon proximity testing with fewer queries , author=. Annual International Cryptology Conference , pages=. 2024 , organization=

work page 2024
[8]

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

On the list-decodability of random linear codes , author=. Proceedings of the forty-second ACM symposium on Theory of computing , pages=

work page
[9]

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

On the list decodability of random linear codes with large error rates , author=. Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages=

work page
[10]

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

Average-radius list-recoverability of random linear codes , author=. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2018 , organization=

work page 2018
[11]

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=

work page 2021
[12]

Cryptology ePrint Archive , year=

From List-Decodability to Proximity Gaps , author=. Cryptology ePrint Archive , year=

work page
[13]

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
[14]

Designs, Codes and Cryptography , volume=

Ligero: lightweight sublinear arguments without a trusted setup , author=. Designs, Codes and Cryptography , volume=. 2023 , publisher=

work page 2023
[15]

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
[16]

Cryptology ePrint Archive , year=

Interactive oracle proofs with constant rate and query complexity , author=. Cryptology ePrint Archive , year=

work page
[17]

Annual International Cryptology Conference , pages=

BaseFold: efficient field-agnostic polynomial commitment schemes from foldable codes , author=. Annual International Cryptology Conference , pages=. 2024 , organization=

work page 2024
[18]

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=

work page 2025
[19]

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=

work page arXiv
[20]

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=

work page arXiv
[21]

arXiv preprint arXiv:2510.06185 , year=

Probabilistic guarantees to explicit constructions: Local properties of linear codes , author=. arXiv preprint arXiv:2510.06185 , year=

work page arXiv
[22]

Combinatorica , volume=

Explicit subspace designs , author=. Combinatorica , volume=. 2016 , publisher=

work page 2016
[23]

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=

work page 2008
[24]

Theory of Computing , volume=

List-decoding multiplicity codes , author=. Theory of Computing , volume=. 2015 , publisher=

work page 2015
[25]

Cryptology ePrint Archive , year=

A note on mutual correlated agreement for Reed-Solomon codes , author=. Cryptology ePrint Archive , year=

work page
[26]

Cryptology ePrint Archive , year=

On reed--solomon proximity gaps conjectures , author=. Cryptology ePrint Archive , year=

work page
[27]

Cryptology ePrint Archive , year=

Khatam: reducing the communication complexity of code-based SNARKs , author=. Cryptology ePrint Archive , year=

work page
[28]

Cryptology ePrint Archive , year=

All Polynomial Generators Preserve Distance with Mutual Correlated Agreement , author=. Cryptology ePrint Archive , year=

work page
[29]

Guruswami et al.,Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed– Solomon Codes, arXiv:2601.10047, 2026

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

work page arXiv
[30]

On Proximity Gaps for Reed-Solomon Codes , year =

Eli Ben-Sasson and Dan Carmon and Ulrich Hab. On Proximity Gaps for Reed-Solomon Codes , year =

work page
[31]

Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , pages=

Improved low-degree testing and its applications , author=. Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , pages=

work page
[32]

Cryptology ePrint Archive , year=

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

work page