Search papers, labs, and topics across Lattice.
This paper improves the proximity gaps for various random ensembles of error-correcting codes, including random linear codes and Reed-Solomon codes, achieving results that match the near-optimal parameters previously established for subspace design codes. The authors leverage a novel extension of the Local Coordinate-wise Linear (LCL) property framework to establish a row-span constrained version, allowing for a more direct analysis of curve-decodability. This advancement not only enhances the understanding of proximity gaps in these codes but also suggests that future progress in subspace design codes will benefit random ensembles as well.
Improved proximity gaps for random error-correcting codes now match those of subspace design codes, bridging a significant performance gap.
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.
