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

Q: What problem do proximity gaps and correlated agreement address in code-based proof systems?

They prevent a bad scenario where many sampled points from a structured family are each close to a code, while no single coherent structured family of codewords explains all of them globally.

Q: What is the main proof approach used for random linear codes?

A direct method based on a syndrome-space reformulation combined with a witness-based reduction argument, explicitly avoiding list decoding as the main engine.

Q: What results are obtained for random Reed–Solomon codes?

The same syndrome-space reductions yield correlated agreement for Reed–Solomon codes over affine spaces and polynomial curves up to radius bounds, with specified field-size requirements.

Jul 16, 2026

Upload by Olivia Brown

Proximity gaps and correlated agreement support the local-to-global analysis of interactive oracle proofs of proximity (IOPPs) and code-based SNARKs by ruling out the case where many sampled structured words are individually close to a code yet no coherent structured set explains them globally. The work presents a direct syndrome-space framework for random linear codes in the random parity-check-matrix model, avoiding list-decoding as the main proof engine, and derives sharp bounds for affine lines, affine spaces, and polynomial curves, including optimal-up-to-ε large-alphabet radius guarantees, plus near-capacity results over constant alphabets with improved field-size requirements.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages45

Reading Time1 h 53 min

Introduction

Motivation and background

Proximity-gap and correlated-agreement theorems

Applications to IOPPs and SNARKs

arXiv :2605 .07595v2 [ cs .IT] 10 Jul 2026 A Syndrome-Space Approach to Proximity Gaps and Correlated Agreement for Random Linear Codes and Random Reed–Solomon Codes ∗ Chen Yuan, Ruiqi Zhu 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 by first proving list-decoding-type properties. Random Reed–Solomon codes provide a further natural benchmark, as they retain the algebraic structure of Reed–Solomon codes while introducing randomness through the evaluation set. 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 syndromespace reformulation together with a witness-based reduction argument, 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-ε large-alphabet radius bound ρ < 1 − R − ε for q = Θ(n), as well as near-capacity bounds over constant alphabets with improved alphabet-size requirements. We further apply the same syndrome-space reductions to random Reed–Solomon codes. Since Reed–Solomon parity-check matrices are highly structured, the final random parity-check union bound is replaced by a local-profile argument. This yields ∗ C. Yuan is with School of Computer Science, Shanghai Jiao Tong University. (Email: [chen_yuan@sjtu.edu.cn](chen_yuan@sjtu.edu.cn)) R. Zhu is with School of Computer Science, Shanghai Jiao Tong University.(Email: [sjtuzrq7777@sjtu.edu.cn](sjtuzrq7777@sjtu.edu.cn)) correlated agreement for random Reed–Solomon codes over affine spaces and polynomial curves up to radius ρ ≤ 1 − R − ε, with field size q ≥ n · 2O (ε−3) for affine spacesand q ≥ n · 2Oℓ (ε−3) for degree-ℓ curves. 1 Introduction Proximity gaps, introduced by [RVW13], capture a basic local-to-global phenomenon for codes and have become important in the analysis of interactive oracle proofs of proximity (IOPPs) and code-based SNARKs. In protocols such as FRI and DEEP-FRI [BSBHR18, BSGKS19], and in more recent systems such as STIR and WHIR [ACFY24, ACFY25], theverifier reasons about a structured family of words—for example, a line, an affine space, ora low-degree curve—while querying only a few random locations. For such sampling-based checks to be sound, one needs a code-theoretic statement showing that the following bad situation cannot happen: many sampled points are individually close to the code, yet thereis no single structured family of codewords that explains these nearby points at once. This is exactly the content of proximity-gap and correlated-agreement theorems. Informally, a proximity-gap theorem says that if too many points of a structured family are within distance ρn of a code C, then the whole family must lie inside a slightly larger neighborhood of C. A

FAQs

What problem do proximity gaps and correlated agreement address in code-based proof systems?

They prevent a bad scenario where many sampled points from a structured family are each close to a code, while no single coherent structured family of codewords explains all of them globally.

What is the main proof approach used for random linear codes?

A direct method based on a syndrome-space reformulation combined with a witness-based reduction argument, explicitly avoiding list decoding as the main engine.

What results are obtained for random Reed–Solomon codes?

The same syndrome-space reductions yield correlated agreement for Reed–Solomon codes over affine spaces and polynomial curves up to radius bounds, with specified field-size requirements.

Jul 16, 2026

Upload by Olivia Brown