Search Results

Documents authored by Goyal, Rohan

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.61
Locality of Curve-Decoding and Improved Proximity Gaps

Authors: Rohan Goyal, Venkatesan Guruswami, Yihang Sun, and Mary Wootters

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract
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.
Cite as

Rohan Goyal, Venkatesan Guruswami, Yihang Sun, and Mary Wootters. Locality of Curve-Decoding and Improved Proximity Gaps. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 61:1-61:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{goyal_et_al:LIPIcs.APPROX/RANDOM.2026.61,
  author =	{Goyal, Rohan and Guruswami, Venkatesan and Sun, Yihang and Wootters, Mary},
  title =	{{Locality of Curve-Decoding and Improved Proximity Gaps}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{61:1--61:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.61},
  URN =		{urn:nbn:de:0030-drops-277784},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.61},
  annote =	{Keywords: Proximity gaps, random codes, curve decoding, local properties}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.67
Fast List Recovery of Univariate Multiplicity Codes

Authors: Rohan Goyal, Prahladh Harsha, Mrinal Kumar, and Ashutosh Shankar

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract
Recent work gave near-linear time algorithms for list decoding Folded Reed-Solomon codes and univariate multiplicity codes up to capacity in their natural parameter regimes. Unlike most known list decoding algorithms, these techniques appeared inherently tied to list decoding, and it was unclear whether they could be extended to list recovery in near-linear time. In this work, we resolve this question by giving Õ(n)-time algorithms for list recovery of Folded Reed-Solomon codes and univariate multiplicity codes up to capacity, where n is the block length. Our algorithms build on the lattice-based framework of the prior work, augmented with a new technical ingredient: the construction of suitably structured lattices over the univariate polynomial ring that capture the list recovery problem for these codes.
Cite as

Rohan Goyal, Prahladh Harsha, Mrinal Kumar, and Ashutosh Shankar. Fast List Recovery of Univariate Multiplicity Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 67:1-67:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{goyal_et_al:LIPIcs.APPROX/RANDOM.2026.67,
  author =	{Goyal, Rohan and Harsha, Prahladh and Kumar, Mrinal and Shankar, Ashutosh},
  title =	{{Fast List Recovery of Univariate Multiplicity Codes}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{67:1--67:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.67},
  URN =		{urn:nbn:de:0030-drops-277840},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.67},
  annote =	{Keywords: list-recovery, multiplicity-codes, near-linear-algorithm}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact