Pith Number

pith:IMJVQH44

pith:2025:IMJVQH44NWT4IAOFQQITXXW3F6

not attested not anchored not stored refs resolved

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

Chen Yuan, Ruiqi Zhu

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

arxiv:2511.04135 v2 · 2025-11-06 · cs.IT · cs.CR · math.IT

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{IMJVQH44NWT4IAOFQQITXXW3F6}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

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−√r.

C2weakest assumption

The algebraic properties of Galois rings (in particular their module structure and root-finding behavior) permit the same interpolation and factorization steps used over fields to succeed with identical radius guarantees.

C3one line summary

Extends list decoding of Reed-Solomon and folded Reed-Solomon codes to Galois rings, achieving radius 1-sqrt(r) and Singleton-bound performance with list size O(1/ε²).

References

5 extracted · 5 resolved · 0 Pith anchors

[1] Proximity gaps for reed-solomon codes 2020

[2] Fast reed- solomon interactive oracle proofs of proximity 2018

[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, e 2023

[4] Poly- nomial commitments for galois rings and applications to snarks overZ2k 2025

[5] Improved list size for folded reed-solomon codes 2025

Formal links

2 machine-checked theorem links

Receipt and verification

First computed	2026-05-18T03:09:33.538706Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

4313581f9c6da7c401c584113bdedb2f884612632abd205aab7b7fcc6542754e

Aliases

arxiv: 2511.04135 · arxiv_version: 2511.04135v2 · doi: 10.48550/arxiv.2511.04135 · pith_short_12: IMJVQH44NWT4 · pith_short_16: IMJVQH44NWT4IAOF · pith_short_8: IMJVQH44

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/IMJVQH44NWT4IAOFQQITXXW3F6 \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 4313581f9c6da7c401c584113bdedb2f884612632abd205aab7b7fcc6542754e

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "6a5c1a61c2483bc3a25ebfab625558a581cbbfa2a28e1a61f47e6b42ffa2373f",
    "cross_cats_sorted": [
      "cs.CR",
      "math.IT"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "cs.IT",
    "submitted_at": "2025-11-06T07:23:12Z",
    "title_canon_sha256": "1b5e8ae54908d745f463a5013c6977720f286fe8ad42d58c86641fd13bbd0707"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2511.04135",
    "kind": "arxiv",
    "version": 2
  }
}