Improved LCL Equivalences and Curve Decoding Alphabet Sizes

Abstract

Local Coordinate-wise Linear (LCL) properties, introduced by Levi, Mosheiff, and Shagrithaya (2025), capture coding-theoretic properties such as list decoding and list recovery. They showed that every LCL property has the same rate threshold for random linear codes (RLC) and random Reed--Solomon codes (RRS). Brakensiek, Chen, Dhar, and Zhang (2025) extended this to random additive codes. Thus any property of all subspace design codes holds for RLCs and RRS at the same rate. In this work, we improve the probabilistic guarantees in the RRS local equivalence theorem and extend the equivalence to all known subspace design constructions individually. Each such construction, including folded Reed--Solomon codes, has the same LCL threshold as RLC and RRS codes. We apply these results to alphabet-size bounds for curve decoding. Curve decoding, introduced by Goyal and Guruswami (2025) and Carmon et al. (2026), is a row-span-constrained LCL property implying proximity gaps (PG), correlated agreement (CA), and mutual correlated agreement (MCA), relevant to IOPs and SNARKs. Informally, a rate-R code C ⊂ 𝔽ⁿ is (ℓ,δ,a,b)-curve decodable if any degree-ℓ curve u:𝔽→𝔽ⁿ that is δ-close to C on at least a points has at least b≤ a nearby codewords lying on a degree-ℓ curve in C. Goyal and Guruswami (2025) and Goyal, Guruswami, Sun, and Wootters (2026) established curve decodability for RLC and RRS codes at radius δ approaching 1−R, but with large alphabets in ℓ and η:=1−R−δ. Using our improved LCL equivalence and rank-sensitive counting inspired by Goyal and Guruswami (2026), we exponentially improve alphabet requirements while matching the best known values of (a,b). For ℓ=O(1), our alphabet-size bounds match the best known for list decoding, and improves results for PG, CA, and MCA.

Improved upper bound on the number of distinct k-decks for any k and alphabet size by counting the independent parameters
Arman Nilforoushan, Farzad Parvaresh
arXiv29 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
P-curve: An improved solution for the single-facility location problem in two regions with ℓ_p- and ℓ_q-norms
Luis Franco, Francisco Velasco, Francisco J. Ortega-Irizo +1
arXiv1 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
An Improved Johnson Bound for List-Decoding with Hints
Swastik Kopparty, Harry Sha
arXiv27 Oct 2026PreprintCC BY-NC-SA 4.0Full textGeneral mathematicsarXiv
The Expected Number of Distinct Substrings in an Alphabet String
Anant Godbole
arXiv16 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics ProbabilityarXiv
Maximizing Measures for Subadditive and Almost-Additive Potentials on Countable-Alphabet Subshifts
Ricardo Freire, Juliano S. Gonschorowski
arXiv23 Oct 2026PreprintarXiv licenceFull textDynamical systemsarXiv

Cite

BibTeX RIS

BibTeX

@misc{goyal2026improved,
  title = {{Improved LCL Equivalences and Curve Decoding Alphabet Sizes}},
  author = {Rohan Goyal and Venkatesan Guruswami and Yihang Sun and Mary Wootters},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.38862},
  eprint = {2610.38862},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.38862},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Improved LCL Equivalences and Curve Decoding Alphabet Sizes
AU  - Rohan Goyal
AU  - Venkatesan Guruswami
AU  - Yihang Sun
AU  - Mary Wootters
PY  - 2026
DA  - 2026/10/28
PB  - arXiv
DO  - 10.48550/arxiv.2610.38862
UR  - https://arxiv.org/abs/2610.38862
AB  - Local Coordinate-wise Linear (LCL) properties, introduced by Levi, Mosheiff, and Shagrithaya (2025), capture coding-theoretic properties such as list decoding and list recovery. They showed that every LCL property has the same rate threshold for random linear codes (RLC) and random Reed--Solomon codes (RRS). Brakensiek, Chen, Dhar, and Zhang (2025) extended this to random additive codes. Thus any property of all subspace design codes holds for RLCs and RRS at the same rate. In this work, we improve the probabilistic guarantees in the RRS local equivalence theorem and extend the equivalence to all known subspace design constructions individually. Each such construction, including folded Reed--Solomon codes, has the same LCL threshold as RLC and RRS codes. We apply these results to alphabet-size bounds for curve decoding. Curve decoding, introduced by Goyal and Guruswami (2025) and Carmon et al. (2026), is a row-span-constrained LCL property implying proximity gaps (PG), correlated agreement (CA), and mutual correlated agreement (MCA), relevant to IOPs and SNARKs. Informally, a rate-R code C ⊂ 𝔽^n is (ℓ,δ,a,b)-curve decodable if any degree-ℓ curve u:𝔽→𝔽^n that is δ-close to C on at least a points has at least b≤ a nearby codewords lying on a degree-ℓ curve in C. Goyal and Guruswami (2025) and Goyal, Guruswami, Sun, and Wootters (2026) established curve decodability for RLC and RRS codes at radius δ approaching 1−R, but with large alphabets in ℓ and η:=1−R−δ. Using our improved LCL equivalence and rank-sensitive counting inspired by Goyal and Guruswami (2026), we exponentially improve alphabet requirements while matching the best known values of (a,b). For ℓ=O(1), our alphabet-size bounds match the best known for list decoding, and improves results for PG, CA, and MCA.
ER  -

Abstract

Related

Cite