Answers are grounded in this paper and cite their sources.
Demonstrates a linear proximity gap in batched Reed-Solomon codes, indicating improved soundness in error correction.
We prove a linear proximity gap (correlated agreement) for batched Reed–Solomon codes over the Galois ring R = GR(2^k, m) of residue characteristic 2, at the unique-decoding radius δ < (1−ρ)/2. For the degree-s batching curve w(α) = Σ αʲ gⱼ with challenges drawn from the Teichmüller set 𝒯 ⊂ R, the correlated-agreement threshold is exactly L = sℓ — identical to the finite-field threshold, independent of the ring depth k and of the distance δ, with zero proximity loss. Building on the batched Reed–Solomon framework of Jia, Li, Xing, Yao and Yuan (CRYPTO 2025), we sharpen their quadratic threshold sℓ² to the linear optimum sℓ. At representative parameters (s, ℓ, m, ρ) = (64, 2²¹, 155, 1/2), the soundness error is ε = sℓ / 2ᵐ = 2⁻¹²⁸ exactly. We also give an affine variant: batching with an independent challenge vector z ∈ 𝒯ˢ, instead of the powers of a single α, removes the factor s — giving threshold ℓ·qˢ⁻¹ and error ℓ / 2ᵐ, independent of the batch size s. The method is a 2-adic descent: reduce modulo 2 to the residue field 𝔽₂ᵐ, apply the field correlated-agreement bound, lift the codewords by an α-independent choice of coefficients, divide the residual exactly by 2, and induct on the ring depth k. The argument never forms the bivariate (Polishchuk–Spielman) object in which the quadratic factor originates, which is what removes the extra factor ℓ.
No takes yet. Share an insight, caveat, or question.
Luis Angel González (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: