pith. sign in

arxiv: 2511.04135 · v2 · pith:IMJVQH44new · submitted 2025-11-06 · 💻 cs.IT · cs.CR· math.IT

List Decoding of Reed-Solomon Codes and Folded Reed-Solomon Codes Over Galois Ring

Chen Yuan , Ruiqi Zhu This is my paper

Pith reviewed 2026-05-18 01:24 UTC · model grok-4.3

classification 💻 cs.IT cs.CRmath.IT
keywords list decodingReed-Solomon codesGalois ringsfolded Reed-Solomon codeserror correction codesSingleton boundproximity gap
0
0 comments X

The pith

Reed-Solomon codes over Galois rings can be list decoded up to radius 1 minus the square root of their rate.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends the Guruswami-Sudan list decoding procedure from finite fields to Galois rings for Reed-Solomon codes. This extension shows that codes with rate r can be list decoded up to radius 1 - sqrt(r). The authors further apply similar ideas to folded Reed-Solomon codes over Galois rings, achieving list decoding radii that approach the Singleton bound. They also improve the list size to O(1/eps^2) and demonstrate that these codes meet a relaxed generalized Singleton bound in the average-radius sense. This work addresses the need for better understanding of proximity gaps in codes over rings, which is relevant for zero-knowledge proof systems using ring arithmetic.

Core claim

By adapting the interpolation and factorization steps of the Guruswami-Sudan algorithm to the module structure of Galois rings, the paper establishes that Reed-Solomon codes over these rings achieve the same list decoding radius of 1 - sqrt(r) as their field counterparts, while folded Reed-Solomon codes over Galois rings attain list decoding up to the Singleton bound with improved list sizes.

What carries the argument

The interpolation polynomial constructed over the Galois ring and the subsequent root-finding procedure that factors it to recover candidate codewords within the decoding radius.

If this is right

  • Reed-Solomon codes over Galois rings support list decoding up to radius 1 - sqrt(r) with polynomial list size.
  • Folded Reed-Solomon codes over Galois rings achieve list decoding radius 1 - r - eps for any eps > 0.
  • The list size for the folded codes can be bounded by O(1/eps^2).
  • These codes satisfy the relaxed generalized Singleton bound on average radius with list size O(1/eps).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This development may support the construction of more efficient zero-knowledge proof systems for arithmetic circuits over rings.
  • The techniques could potentially apply to other code families defined over Galois rings.
  • Further work might explore the computational efficiency of implementing these decoders in practice.

Load-bearing premise

The module structure and root-finding properties of Galois rings allow the interpolation and factorization steps to succeed with the same radius guarantees as over fields.

What would settle it

Finding an explicit Reed-Solomon code over a small Galois ring and a received word with errors within radius 1 - sqrt(r) for which the adapted Guruswami-Sudan procedure outputs a list that misses some valid codeword.

read the original abstract

List decoding of codes can be seen as the generalization of unique decoding of codes While list decoding over finite fields has been extensively studied, extending these results to more general algebraic structures such as Galois rings remains an important challenge. Due to recent progress in zero knowledge systems, there is a growing demand to investigate the proximity gap of codes over Galois rings in Yizhou Yao and coauthors(2025), Alexander Golovne and coauthors(2023), Yuanju Wei and coauthors(2025). The proximity gap is closely related to the decoding capability of codes. It was shown in Eli Ben-Sasson and coauthors(2020) that the proximity gap for RS codes over finite field can be improved to $1-\sqrt{r}$ if one consider list decoding instead of unique decoding. However, we know very little about RS codes over Galois ring which might hinder the development of zero knowledge proof system for ring-based arithmetic circuit. In this work, we first extend the list decoding procedure of Guruswami and Sudan to Reed-Solomon codes over Galois rings, which shows that RS codes with rate $r$ can be list decoded up to radius $1-\sqrt{r}$. Then, we investigate the list decoding of folded Reed-Solomon codes over Galois rings. We show that the list decoding radius of folded Reed-Solomon codes can reach the Singlton bound as its counterpart over finite field. Finally, we improve the list size of our folded Reed-Solomon code to $O(\frac{1}{\varepsilon^2})$ by extending recent work in Shashank Srivastava(2025) to Galois Rings. Moreover, at the combinatorial level, by developing the recent work of Yeyuan Chen and Zihan Zhang(2025), we show that folded Reed-Solomon codes over Galois rings satisfy the relaxed generalized Singleton bound in the average-radius sense with optimal list size $O(1/\varepsilon)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript extends the Guruswami-Sudan list decoding algorithm to Reed-Solomon codes over Galois rings, claiming that codes of rate r can be list decoded up to radius 1−√r. It further extends the approach to folded Reed-Solomon codes over Galois rings, achieving list decoding radius equal to the Singleton bound, an improved list size of O(1/ε²) via extension of recent work, and a combinatorial result showing that these codes meet the relaxed generalized Singleton bound in the average-radius sense with optimal list size O(1/ε).

Significance. If the ring extensions are rigorously established, the results would meaningfully broaden list decoding techniques beyond finite fields, supporting applications in zero-knowledge proofs for ring-based arithmetic circuits and proximity-gap analyses over rings. The work appropriately builds on Guruswami-Sudan, recent proximity-gap papers, and 2025 list-size improvements while targeting the module-theoretic setting.

major comments (1)
  1. [Section describing the interpolation procedure and its correctness over Galois rings] The central interpolation step (in the extension of Guruswami-Sudan to Galois rings): the existence of a non-zero bivariate polynomial Q(X,Y) of controlled bidegree that vanishes to multiplicity s at each interpolation point must be justified over the Galois ring module rather than a vector space. The standard homogeneous linear system counting argument does not automatically carry over because Galois rings have zero-divisors and their modules need not be free; an explicit module rank or invariant-factor argument is required to guarantee a non-trivial solution and thereby support the radius 1−√r guarantee.
minor comments (2)
  1. [Abstract] Citations in the abstract are written in an informal style (e.g., “Yizhou Yao and coauthors(2025)”). Replace with standard author-year or numbered bibliographic references throughout.
  2. [Introduction or preliminaries] Clarify the precise definition of the Galois ring GR(p^k, m) and the module structure used for the codewords at the first appearance of the notation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed and constructive feedback. We agree that the module-theoretic justification for the interpolation step requires explicit treatment due to the structure of Galois rings. We will revise the manuscript to include a rigorous argument establishing the existence of a non-zero bivariate polynomial over the Galois ring module.

read point-by-point responses

  1. Referee: [Section describing the interpolation procedure and its correctness over Galois rings] The central interpolation step (in the extension of Guruswami-Sudan to Galois rings): the existence of a non-zero bivariate polynomial Q(X,Y) of controlled bidegree that vanishes to multiplicity s at each interpolation point must be justified over the Galois ring module rather than a vector space. The standard homogeneous linear system counting argument does not automatically carry over because Galois rings have zero-divisors and their modules need not be free; an explicit module rank or invariant-factor argument is required to guarantee a non-trivial solution and thereby support the radius 1−√r guarantee.

    Authors: We agree with this observation. The presence of zero-divisors in Galois rings means that the standard dimension-counting argument over fields does not directly apply, and the relevant module of bivariate polynomials may require an invariant-factor decomposition to confirm that the interpolation conditions do not force the zero polynomial. In the revised version we will add a dedicated subsection that (i) recalls the structure theorem for finitely generated modules over Galois rings, (ii) shows that the module of polynomials of bidegree at most (D, s) is free of known rank, and (iii) verifies that the number of homogeneous linear conditions imposed by the multiplicity-s vanishing conditions is strictly less than this rank, thereby guaranteeing a non-trivial solution. This addition will directly support the claimed list-decoding radius of 1−√r. revision: yes

Circularity Check

0 steps flagged

Derivation extends Guruswami-Sudan via independent module analysis over rings

full rationale

The paper states it extends the Guruswami-Sudan interpolation and factorization procedure to Reed-Solomon codes over Galois rings while preserving the 1-sqrt(r) radius, citing the algebraic properties of Galois rings (module structure and root-finding) as permitting the same steps. No quoted step reduces the radius guarantee or list-size bound to a self-definition, a fitted parameter renamed as prediction, or a load-bearing self-citation chain; the central claims are presented as new analysis rather than by-construction substitution of the field case. External citations (Ben-Sasson et al. 2020, Srivastava 2025, Chen-Zhang 2025) are to distinct prior works and do not form a closed self-referential loop within this manuscript. The derivation is therefore self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on the assumption that standard algebraic properties of Galois rings suffice to carry over the finite-field proofs; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Galois rings admit the same interpolation and root-finding operations used in the Guruswami-Sudan algorithm over fields.
    Invoked when extending the list-decoding procedure to rings.

pith-pipeline@v0.9.0 · 5899 in / 1355 out tokens · 44632 ms · 2026-05-18T01:24:28.782543+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages

  1. [1]

    Proximity gaps for reed-solomon codes

    [BCI+20] Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf. Proximity gaps for reed-solomon codes. In Sandy Irani, editor,61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 900–909. IEEE,

    work page 2020

  2. [2]

    Fast reed- solomon interactive oracle proofs of proximity

    [BSBHR18] Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast reed- solomon interactive oracle proofs of proximity. In45th international collo- quium on automata, languages, and programming (icalp 2018), pages 14–1. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik,

    work page 2018

  3. [3]

    [GLS+23] Alexander Golovnev, Jonathan Lee, Srinath T. V. Setty, Justin Thaler, and Riad S. Wahby. Brakedown: Linear-time and field-agnostic snarks for R1CS. In Helena Handschuh and Anna Lysyanskaya, editors,Advances in Cryp- tology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Pro...

    work page 2023

  4. [4]

    Poly- nomial commitments for galois rings and applications to snarks overZ2k

    [JLX+25] Yuhao Jia, Songsong Li, Chaoping Xing, Yizhou Yao, and Chen Yuan. Poly- nomial commitments for galois rings and applications to snarks overZ2k. In Advances in Cryptology – CRYPTO 2025, volume 16005 ofLecture Notes in Computer Science, pages 515–548. Springer,

    work page 2025

  5. [5]

    Improved list size for folded reed-solomon codes

    [Sri25] Shashank Srivastava. Improved list size for folded reed-solomon codes. InPro- ceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2040–2050. SIAM,

    work page 2025