2026-09-10T09:44:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27778 2026-09-09T12:19:38Z ddc:004 open_access

Locality of Curve-Decoding and Improved Proximity Gaps Goyal, Rohan Guruswami, Venkatesan Sun, Yihang Wootters, Mary Proximity gaps random codes curve decoding local properties 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). Informally, we say that a code C ⊂ Σⁿ exhibits a proximity gap (with respect to degree-𝓁 curves) if for any degree-𝓁 curve u(x) ∈ Σⁿ, either every point on u(x) is close to C, or else most of them are far from C. Recent work [Goyal and Guruswami, 2025] 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. However, the parameters for these latter randomized ensembles are worse than the parameters for subspace design codes, and degrade as the degree 𝓁 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, 2025] 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 in [Levi et al., 2025; Brakensiek et al., 2025] to a row-span constrained version. This allows us to cast curve-decodability - a property that implies proximity gaps - directly as an (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. In addition, we extend the framework to also show an equivalence theorem for Gallager’s ensemble of random LDPC codes and random linear codes for our row-span constrained LCL properties. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rohan Goyal and Venkatesan Guruswami and Yihang Sun and Mary Wootters 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.61 urn:nbn:de:0030-drops-277784 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.61 eng https://creativecommons.org/licenses/by/4.0/legalcode