Efficient Decoding of Twisted GRS Codes and Roth-Lempel Codes

Lingfei Jin; Runtian Zhu

REVIEW 3 major objections 3 minor 49 references

Efficient Decoding of Twisted GRS Codes and Roth-Lempel Codes

T0 review · 3 major / 3 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Non-GRS MDS codes can be decoded near-linearly by embedding them in generalized Reed–Solomon codes and filtering the Guruswami–Sudan list.

desk verdict Clean reductions of TGRS and Roth–Lempel decoding to GRS decoding, with the first RL decoder and multi-twist TGRS support; just mind the gap between the abstract's two complexity claims. read the letter →

arxiv 2512.24217 v2 pith:VP5SC2ZG submitted 2025-12-30 cs.IT math.IT

Runtian Zhu , Lingfei Jin This is my paper · ORCID

classification cs.ITmath.IT MSC 94B0594B35

keywords twistedgeneralizedReed–SolomoncodesRoth–LempelGuruswami–SudanalgorithmlistdecodinguniqueMDSalgebraicmanipulationdetectionnear-linear

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper aims to show that twisted generalized Reed–Solomon (TGRS) codes and Roth–Lempel codes — two families of maximum-distance-separable codes known not to be equivalent to Reed–Solomon codes — can be decoded efficiently by embedding them into ordinary generalized Reed–Solomon (GRS) codes and running the Guruswami–Sudan list decoder on the ambient code. A TGRS code sits inside a GRS code of slightly larger pseudo-dimension k'=k+max_i t_i, and decoding the ambient GRS code followed by a twist-coefficient check returns exactly the TGRS codewords within the decoding radius. Puncturing a Roth–Lempel code at its last coordinate turns it into a GRS code, so the same strategy works with a re-encoding and distance filter. Under fixed-rate conditions the resulting decoders run in near-linear time, correct beyond the classical unique-decoding radius, and give what appears to be the first efficient decoder for Roth–Lempel codes. Algebraic manipulation detection codes are then layered on to recover a unique message from the output list with high probability.

What carries the argument

The load-bearing object is the pseudo-dimension k'=k+max_i t_i, the dimension of the smallest GRS code containing a given TGRS code; it lifts the twisted polynomial space into F_q[x]_{<k'}. The twist-coefficient check rebuilds each candidate from its first k coefficients plus twist terms and rejects it unless it matches exactly, implementing membership in the TGRS code. For Roth–Lempel codes, the puncturing relation — deleting the last coordinate gives C_GRS(α,v',k) — converts decoding into GRS list decoding followed by re-encoding and Hamming-distance filtering. The Guruswami–Sudan algorithm is the workhorse: it interpolates a bivariate polynomial through the received points and finds all l

What would settle it

For a fixed rate, say k=n/2 with pseudo-dimension k'=n/2, search (by exhaustive or randomized computation) for a received word r at distance less than n−√(n k') from a valid TGRS codeword for which Algorithm 2 either omits a valid codeword or returns a polynomial not in P_TGRS(k,T); one such word disproves Theorem 2. Separately, benchmark the cited fast Guruswami–Sudan implementation on dimensions k'=ρn for fixed ρ; if its per-symbol time grows faster than polylogarithmically in n, the claimed O(n log^2 n log log n) complexity does not hold in the regime the decoder needs.

Watch

Extended reading notes

Core claim

The central discovery is structural: every twisted GRS code is a subcode of an ordinary GRS code of pseudo-dimension k'=k+max_i t_i, and every Roth–Lempel code punctured at its last coordinate is a GRS code. Because of this, the Guruswami–Sudan list decoder can be run on the larger GRS code, and an inexpensive filter — checking twist equations for TGRS, or re-encoding and comparing distances for Roth–Lempel — selects exactly the codewords of the non-GRS code inside the decoding radius. The resulting list decoders handle up to τ<n−√(n k') errors for TGRS and τ<(n−1)−√((n−1)k) for Roth–Lempel, radii that exceed half the minimum distance under the stated parameter conditions; unique decoders at

Load-bearing premise

The near-linear running time is inherited from an imported fast implementation of the Guruswami–Sudan algorithm whose complexity the paper cites rather than proves, and if that implementation has a hidden dependence on n/k' (or extra field-size or preprocessing requirements) in the fixed-rate pseudo-dimension regime, the advertised speedup over quadratic-time decoders fails.

Editorial extensions

If this is right

For fixed-rate MDS TGRS codes, unique decoding at the optimal radius (n−k)/2 is achieved in near-linear time when k' < (n+k)^2/(4n), and the decoder tolerates a super-constant number of twists — up to ℓ=O(n log^2 n log log n) within the advertised time budget.
The TGRS list decoder exceeds the classical unique-decoding radius whenever k' < (n+k)^2/(4n), since n−√(n k') is then larger than (n−k)/2; previous TGRS decoders only handled unique decoding.
Roth–Lempel codes, which had no published decoder, now have list and unique decoders; unique decoding at half the minimum distance holds when √(n−1)−√k > 1.
AMD preencoding with four redundancy symbols converts list decoding into unique decoding with error probability O(1/q), at the same decoding radius and with no change to the asymptotic running time.
For fixed rate and fixed multiplicity, the output list size is bounded by a constant, so the decoders are practical in the asymptotic sense.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The subcode-of-GRS view is generic: any code that is a subcode of a GRS code with an efficient membership test inherits a Guruswami–Sudan-based list decoder, so other non-GRS MDS constructions may be decodable by the same template.
The near-linear time claim is twist-budget-sensitive: with the maximum ℓ=O(n^2) twists the filter step alone costs O(ℓ), so the genuinely near-linear regime is ℓ=O(n log^2 n log log n); keeping the twist count inside that range appears necessary for the advertised speed.
Because the decoder now handles super-constant twist counts, code-based cryptosystems that trusted many twists for security can no longer assume that structural obscurity by itself blocks decoding.
The AMD block-size parameter b gives a tunable trade-off between rate loss and list-collision probability (error about 4s/q at b=2), and the same packing trick should transfer to any GRS-subcode family with a verifiable membership predicate.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Worth a careful read. The two main reductions are correct and simple: every TGRS code is a subcode of a GRS with pseudo-dimension k′ = k + max t_i, and every Roth–Lempel code punctures to a GRS. The paper uses those to turn Guruswami–Sudan into a decoder for both families, with a coefficient filter for TGRS and a re-encode-and-distance filter for RL. The proofs are clean. Theorem 2 and Theorem 7 really do give exactly the list of valid polynomials whose codewords are within radius τ, and the parameter conditions for unique decoding are derived correctly. The AMD-assisted disambiguation is a straightforward extension of Guruswami–Smith, but the error-probability calculation is explicit and honest.

The main caveat is the complexity claim. The near-linear running time is imported wholesale from Alekhnovich's theorem, quoted as O((s n/k)^{O(1)} n log^2 n log log n). That theorem is published, so this is not a fatal gap, and for fixed rate the factor is constant as stated. The stress-test worry about hidden n/k factors does not quite land: the factor is in the theorem, not hidden. But it is worth a referee checking that Alekhnovich's algorithm indeed runs in that time in the pseudo-dimension regime used here, since the paper gives no proof or re-derivation.

The bigger presentation issue is the abstract. It says the decoder supports up to O(n^2) twists and also that the algorithms run in near-linear time. A reader can miss that these are separate: the O(n^2) twist support is a correctness condition for unique decoding, while near-linear runtime requires ℓ = O(n log^2 n log log n). The paper is explicit later, but the abstract is misleading. That should be fixed.

One more minor point: for Roth–Lempel, the decoding radius (n−1) − √((n−1)k) is what puncturing gives, so the gain over GRS is the family itself, not the radius. That is not a flaw.

Overall the central reductions hold up, the paper gives the first RL decoders and extends TGRS decoding from single-twist quadratic to multi-twist with a near-linear regime, and I do not see a load-bearing flaw. I would cite it. It deserves a serious referee: the math is correct and the contribution is concrete, even if a referee should push on the complexity black box and the abstract's framing.

Referee Report

3 major / 3 minor

Summary. The paper develops list, unique, and AMD-assisted decoding algorithms for twisted generalized Reed-Solomon (TGRS) codes and Roth-Lempel (RL) codes. For TGRS codes, the code is viewed as a subcode of a GRS code with pseudo-dimension k'=k+max_i t_i; Algorithm 2 runs the Guruswami-Sudan (GS) decoder on the GRS supercode and filters candidates by the twist-coefficient condition. Theorem 2 shows the output is exactly the set of valid twist polynomials within distance τ whenever τ<n−sqrt(nk'). Algorithms 3, 7, and 8 give unique decoders with optimal radius under explicit parameter conditions, and Section IV adds an AMD-based mechanism for recovering a unique message from the list. For Roth-Lempel codes, Lemma 7 shows that puncturing the last coordinate yields a GRS code of dimension k; Algorithm 7 decodes the punctured GRS code and re-encodes/filters candidates. Theorems 7 and 9 establish the list and unique decoding radii, and Theorem 10 claims an AMD-assisted variant. The stated complexity is O(n log^2 n log log n) for fixed-rate codes and constant multiplicity, imported from Alekhnovich's fast GS implementation.

Significance. If the claims hold, this is a substantial advance: it provides the first explicit decoders for Roth-Lempel codes, extends TGRS decoding from the single-twist regime to super-constant twists, and surpasses the classical unique-decoding radius. The structural reductions are clean and the correctness arguments are largely straightforward: the TGRS filtering via f=f' is sound, and the RL puncturing argument is correct. The AMD extension is a useful addition with an explicit error-probability trade-off. The complexity claims, however, depend on a black-box theorem and need precise substantiation. There are no fitted parameters or circular arguments; the external GS and AMD results are used appropriately.

major comments (3)

[§III.C, Theorem 1 (also Theorems 3, 6, 8)] The near-linear complexity bound O((sn/k)^{O(1)} n log^2 n log log n) is the paper's headline improvement, but it is imported entirely from [37] without proof or an exact statement of the cited theorem. The authors should provide either a proof or a precise quotation of the theorem, confirming that the O(1) exponent is absolute and that the algorithm applies with multiplicity s and decoding radius τ≤n−sqrt(nk(1+1/s)) in the regime k=Θ(n). Since Theorems 3 and 8 and the abstract rely on this bound, the current citation-only treatment leaves a load-bearing gap.
[§V.E, Theorem 10] The 'In particular' fixed-s radius is incorrect: after τ<(n−1)−sqrt((n−1)(k+2b)), the guaranteed radius should be τ≤(n−1)−sqrt((n−1)(k+2b)(1+1/s)), not τ≤(n−1)−sqrt((n−1)k(1+1/s)). Using k instead of k+2b overstates the decoding radius. The error-probability formula later in the theorem consistently uses k+2b, so this appears to be a typo, but it must be fixed.
[Abstract and §III.D (Remarks 1–2)] The abstract says the TGRS decoder supports up to O(n^2) twists while achieving near-linear time, but these two statements cannot hold simultaneously. Theorem 3 gives complexity O((sn/k')^{O(1)}(n log^2 n log log n+ℓ)); near-linear time requires ℓ=O(n log^2 n log log n). For ℓ=Θ(n^2), the runtime is quadratic. The abstract and conclusion should separate the two regimes: near-linear for ℓ=O(n log^2 n log log n), and support up to ℓ=O(n^2) with the corresponding complexity.

minor comments (3)

[Theorems 2, 4, 5, 7] The phrase 'the guaranteed decoding radius is at most τ≤...' is logically inverted; it should read 'the algorithm succeeds for every τ≤...' or 'the guaranteed decoding radius is at least ...'.
[§IV, Algorithm 5 and Theorem 5] When the code dimension is increased to k+2b and the same twist set T is reused, Definition 1 requires t_i≤n−(k+2b) for every i. The paper should state this parameter condition explicitly; otherwise the TGRS code in the AMD-assisted scheme may not be well-defined.
[Table II and general formatting] Table II appears garbled in the submitted text, with overlapping entries in the Guruswami-Sudan row. Please check the table formatting.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the decoding results reduce to external Guruswami–Sudan/Alekhnovich and AMD results, not to the paper's own fitted values or self-citations.

full rationale

The paper's derivation chain is self-contained in the relevant sense: the TGRS decoder relies on the structural inclusion P_TGRS(k,T) ⊆ F_q[x]_{<k'} (Lemma 4), which is immediate from the definition of the twisted polynomial space, and the subsequent coefficient check is an exact membership test rather than a fitted prediction. The Roth–Lempel decoder relies on Lemma 7, which is proved directly from the generator matrix by deleting the last column. In both cases the claimed output lists are shown to coincide exactly with the decoded candidates by elementary set-theoretic equalities, not by construction of the output. The list-decoding radii, list-size bounds, and complexity statements are imported from the external Guruswami–Sudan and Alekhnovich results (Theorem 1 and Lemma 1), and the AMD-assisted recovery uses the external AMD construction and soundness bound (Lemma 3). These are independent, citeable prior results, not the present authors' own theorems invoked to force the conclusion. The only self-citation, reference [2] by L. Jin, is a background MDS-code construction and is not load-bearing in any decoding proof. The near-linear complexity claim does depend on the unexamined parameter regime and hidden constants of Alekhnovich's algorithm, but that is a correctness/complexity-assumption risk, not circularity: it does not make the derived claim equivalent to its input by definition or by self-reference. No fitted parameters, no renamed known results, and no author-imported uniqueness theorems appear in the derivation. Honest non-finding: score 0.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

No fitted constants or data. The two algorithm parameters (GS multiplicity s, AMD block size b) are explicit user trade-offs, not ad hoc fits. The core radii and complexities are derived from external theorems (GS/Alekhnovich, AMD) used as black boxes. The main internal assumptions are the MDS property of the codes to be uniquely decoded and independence of the channel error from the AMD randomness.

free parameters (2)

GS multiplicity s
Standard Guruswami-Sudan parameter controlling decoding radius against list size and time. It is user-chosen and explicitly traded off, not fitted to data.
AMD block size b
Trade-off parameter between redundancy (2b extra symbols) and decoding error probability O(1/q^b). User-chosen, not fitted to data.

assumptions (5)

standard math Guruswami-Sudan list-decoding theorem with Alekhnovich's near-linear implementation (Theorem 1, refs [35]-[37])
The entire decoding-radius and complexity claims for the GRS supercode are imported from this cited result. Without it the near-linear claims fail.
standard math Systematic AMD code construction and soundness bound of Lemma 3 (Cramer-Fehr-Padrò [46])
The probabilistic unique-recovery guarantee depends on this external construction and its (k+1)/q error bound.
standard math Evaluation of polynomials of degree < k' on n distinct points is injective when n ≤ q
Needed for the filtering step to identify polynomials from codewords; standard property of GRS evaluation maps.
domain assumption The channel error e is fixed independently of the AMD randomness x'
Required so each candidate manipulation δ_j is fixed and the AMD bound applies. If an adversary chooses e after seeing x', the error-probability bound breaks.
domain assumption Existence of MDS TGRS and Roth-Lempel codes with the stated pseudo-dimension bounds
The unique-decoding theorems apply to MDS instances; the paper does not construct such codes, only decodes them if they exist.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Efficient Decoding of Twisted GRS Codes and Roth-Lempel Codes." pith.science (2026). https://pith.science/paper/VP5SC2ZG

@misc{pith2026251224217,
  author       = {Pith},
  title        = {Pith review of: Efficient Decoding of Twisted GRS Codes and Roth-Lempel Codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VP5SC2ZG}},
  note         = {Machine review of arXiv:2512.24217}
}

read the original abstract

MDS codes play a central role in practice due to their broad applications. To date, most known MDS codes are generalized Reed-Solomon (GRS) codes, leaving codes that are not equivalent to GRS codes comparatively less understood. Studying this non-GRS regime is therefore of intrinsic theoretical interest, and is also practically relevant since the strong algebraic structure of GRS codes can be undesirable in cryptographic settings. Among the known non-GRS codes, twisted generalized Reed-Solomon (TGRS) codes and Roth-Lempel codes are two representative families of non-GRS codes that have attracted significant attention. Though substantial work has been devoted to the construction and structural analysis of TGRS and Roth-Lempel codes, comparatively little attention has been paid to their decoding, and many problems remain open. In this paper, we propose list and unique decoding algorithms for TGRS codes and Roth-Lempel codes based on the Guruswami-Sudan algorithm. Under suitable parameter conditions, our algorithms achieve near-linear running time in the code length, improving upon the previously best-known quadratic-time complexity. Our TGRS decoder supports fixed-rate TGRS codes with up to O(n^2) twists, substantially extending prior work that only handled the single-twist case. For Roth-Lempel codes, we provide what appears to be the first efficient decoder. Moreover, our list decoders surpass the classical unique-decoding radius for a broad range of parameters. Finally, we incorporate algebraic manipulation detection (AMD) codes into the list-decoding framework, enabling recovery of the correct message from the output list with high probability.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 5 linked inside Pith

[37]

Linear diophantine equations over polynomials and soft decoding of reed-solomon codes,

M. Alekhnovich, “Linear diophantine equations over polynomials and soft decoding of reed-solomon codes,” inThe 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.IEEE, 2002, pp. 439–448

2002
[1]

New mds or near-mds self-dual codes,

T. A. Gulliver, J.-L. Kim, and Y . Lee, “New mds or near-mds self-dual codes,”IEEE transactions on information theory, vol. 54, no. 9, pp. 4354–4360, 2008

2008
[2]

Construction of mds codes with complementary duals,

L. Jin, “Construction of mds codes with complementary duals,”IEEE Transactions on Information Theory, vol. 63, no. 5, pp. 2843–2847, 2016

2016
[3]

New constructions of mds euclidean self-dual codes from grs codes and extended grs codes,

W. Fang and F.-W. Fu, “New constructions of mds euclidean self-dual codes from grs codes and extended grs codes,”IEEE Transactions on Information Theory, vol. 65, no. 9, pp. 5574–5579, 2019

2019
[4]

New lcd mds codes constructed from generalized reed–solomon codes,

X. Shi, Q. Yue, and S. Yang, “New lcd mds codes constructed from generalized reed–solomon codes,”Journal of Algebra and Its Applications, vol. 18, no. 08, p. 1950150, 2019

2019
[5]

Construction of mds self-dual codes from orthogonal matrices,

M. Shi, L. Sok, and P. Sol ´e, “Construction of mds self-dual codes from orthogonal matrices,”arXiv preprint arXiv:1610.07736, 2016

arXiv 2016
[6]

Several classes of galois self-orthogonal mds codes and related applications,

Y . Li, Y . Su, S. Zhu, S. Li, and M. Shi, “Several classes of galois self-orthogonal mds codes and related applications,”Finite Fields and Their Applications, vol. 91, p. 102267, 2023

2023
[7]

On insecurity of cryptosystems based on generalized reed-solomon codes,

V . M. Sidelnikov and S. O. Shestakov, “On insecurity of cryptosystems based on generalized reed-solomon codes,”Discrete Mathematics and Applications, vol. 2, no. 4, pp. 439–444, 1992

1992

Show all 49 references

[8]

An attack on a modified niederreiter encryption scheme,

C. Wieschebrink, “An attack on a modified niederreiter encryption scheme,” inInternational Workshop on Public Key Cryptography. Springer, 2006, pp. 14–26

2006
[9]

Twisted reed-solomon codes,

P. Beelen, S. Puchinger, and J. R. n ´e Nielsen, “Twisted reed-solomon codes,” in2017 IEEE International Symposium on Information Theory (ISIT). IEEE, 2017, pp. 336–340

2017
[10]

Twisted reed–solomon codes,

P. Beelen, S. Puchinger, and J. Rosenkilde, “Twisted reed–solomon codes,”IEEE transactions on information theory, vol. 68, no. 5, pp. 3047–3061, 2022

2022
[11]

Mds and near-mds codes via twisted reed–solomon codes,

J. Sui, X. Zhu, and X. Shi, “Mds and near-mds codes via twisted reed–solomon codes,”Designs, Codes and Cryptography, vol. 90, no. 8, pp. 1937–1958, 2022

1937
[12]

On parity-check matrices of twisted generalized reed–solomon codes,

W. Cheng, “On parity-check matrices of twisted generalized reed–solomon codes,”IEEE Transactions on Information Theory, vol. 70, no. 5, pp. 3213–3225, 2023

2023
[13]

Construction of mds twisted reed–solomon codes and lcd mds codes,

H. Liu and S. Liu, “Construction of mds twisted reed–solomon codes and lcd mds codes,”Designs, Codes and Cryptography, vol. 89, no. 9, pp. 2051–2065, 2021. 18
[14]

Mds or nmds lcd codes from twisted reed-solomon codes,

D. Huang, Q. Yue, and Y . Niu, “Mds or nmds lcd codes from twisted reed-solomon codes,”Cryptography and communications, vol. 15, no. 2, pp. 221–237, 2023

2023
[15]

Two classes of twisted generalized reed-solomon codes with two twists,

S. Yang, J. Wang, and Y . Wu, “Two classes of twisted generalized reed-solomon codes with two twists,”Finite Fields and Their Applications, vol. 104, p. 102595, 2025

2025
[16]

Twisted reed–solomon codes with one-dimensional hull,

Y . Wu, “Twisted reed–solomon codes with one-dimensional hull,”IEEE Communications Letters, vol. 25, no. 2, pp. 383–386, 2020

2020
[17]

Self-orthogonal generalized twisted reed-solomon codes,

C. Zhu and Q. Liao, “Self-orthogonal generalized twisted reed-solomon codes,”arXiv preprint arXiv:2201.02758, 2022

2022 arXiv
[18]

The (+)-(l, p)-tgrs code,

Z. Liang, C. Jia, and Q. Liao, “The (+)-(l, p)-tgrs code,”arXiv preprint arXiv:2511.03398, 2025

2025
[19]

Mds or nmds self-dual codes from twisted generalized reed–solomon codes,

D. Huang, Q. Yue, Y . Niu, and X. Li, “Mds or nmds self-dual codes from twisted generalized reed–solomon codes,”Designs, Codes and Cryptography, vol. 89, no. 9, pp. 2195–2209, 2021

2021
[20]

A class of twisted generalized reed–solomon codes,

J. Zhang, Z. Zhou, and C. Tang, “A class of twisted generalized reed–solomon codes,”Designs, Codes and Cryptography, vol. 90, no. 7, pp. 1649–1658, 2022

2022
[21]

New constructions of self-dual codes via twisted generalized reed-solomon codes,

J. Sui, Q. Yue, and F. Sun, “New constructions of self-dual codes via twisted generalized reed-solomon codes,”Cryptography and Communications, vol. 15, no. 5, pp. 959–978, 2023

2023
[22]

A construction of non-reed-solomon type mds codes,

R. M. Roth and A. Lempel, “A construction of non-reed-solomon type mds codes,”IEEE transactions on information theory, vol. 35, no. 3, pp. 655–657, 1989

1989
[23]

New lcd mds codes of non-reed-solomon type,

Y . Wu, J. Y . Hyun, and Y . Lee, “New lcd mds codes of non-reed-solomon type,”IEEE Transactions on Information Theory, vol. 67, no. 8, pp. 5069–5078, 2021

2021
[24]

Roth–lempel nmds codes of non-elliptic-curve type,

D. Han and C. Fan, “Roth–lempel nmds codes of non-elliptic-curve type,”IEEE Transactions on Information Theory, vol. 69, no. 9, pp. 5670–5675, 2023

2023
[25]

More mds codes of non-reed-solomon type,

Y . Wu, Z. Heng, C. Li, and C. Ding, “More mds codes of non-reed-solomon type,”arXiv preprint arXiv:2401.03391, 2024

2024 arXiv
[26]

The extended code for a class of generalized roth-lempel codes and their properties,

Z. Liang and Q. Liao, “The extended code for a class of generalized roth-lempel codes and their properties,”arXiv preprint arXiv:2508.12302, 2025

2025 arXiv
[27]

List decoding for noisy channels,

P. Elias, “List decoding for noisy channels,” 1957

1957
[28]

List decoding,

J. M. Wozencraft, “List decoding,”Quarterly Progress Report, vol. 48, pp. 90–95, 1958

1958
[29]

E. R. Berlekamp,Nonbinary BCH decoding. University of North Carolina. Department of Statistics, 1966

1966
[30]

A method for solving key equation for decoding goppa codes,

Y . Sugiyama, M. Kasahara, S. Hirasawa, and T. Namekawa, “A method for solving key equation for decoding goppa codes,”Information and Control, vol. 27, no. 1, pp. 87–99, 1975

1975
[31]

Error correction for algebraic block codes,

L. R. Welch and E. R. Berlekamp, “Error correction for algebraic block codes,” Dec. 30 1986, uS Patent 4,633,470

1986
[32]

Error-locating pairs for cyclic codes,

I. M. Duursma and R. Kotter, “Error-locating pairs for cyclic codes,”IEEE Transactions on Information Theory, vol. 40, no. 4, pp. 1108–1121, 2002

2002
[33]

List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound,

V . Guruswami and C. Xing, “List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound,” inProceedings of the forty-fifth annual ACM symposium on Theory of computing, 2013, pp. 843–852

2013
[34]

Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets,

——, “Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets,” inProceedings of the Twenty-Fifth Annual ACM- SIAM Symposium on Discrete Algorithms. SIAM, 2014, pp. 1858–1866

2014
[35]

Decoding of reed solomon codes beyond the error-correction bound,

M. Sudan, “Decoding of reed solomon codes beyond the error-correction bound,”Journal of complexity, vol. 13, no. 1, pp. 180–193, 1997

1997
[36]

Improved decoding of reed-solomon and algebraic-geometric codes,

V . Guruswami and M. Sudan, “Improved decoding of reed-solomon and algebraic-geometric codes,” inProceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280). IEEE, 1998, pp. 28–37

1998
[38]

Decoding algorithms of twisted grs codes and twisted goppa codes,

H. Sun, Q. Yue, X. Jia, and C. Li, “Decoding algorithms of twisted grs codes and twisted goppa codes,”IEEE Transactions on Information Theory, 2024

2024
[39]

Improved decoding algorithms for mds and almost-mds codes from twisted grs codes,

G. Wang, H. Liu, and J. Luo, “Improved decoding algorithms for mds and almost-mds codes from twisted grs codes,”IEEE Transactions on Information Theory, 2025

2025
[40]

Coding properties and automorphism groups of two classes of twisted generalized reed–solomon codes,

X. Jia, Q. Yue, and H. Sun, “Coding properties and automorphism groups of two classes of twisted generalized reed–solomon codes,”Designs, Codes and Cryptography, pp. 1–27, 2025

2025
[41]

Decoding algorithms for twisted grs codes,

G. Zhang, L. Lin, and B. Chen, “Decoding algorithms for twisted grs codes,”arXiv preprint arXiv:2508.03552, 2025

2025 arXiv
[42]

The error-correcting pair for tgrs codes,

B. He and Q. Liao, “The error-correcting pair for tgrs codes,”Discrete Mathematics, vol. 346, no. 9, p. 113497, 2023

2023
[43]

Cryptanalysis of a system based on twisted reed–solomon codes,

J. Lavauzelle and J. Renner, “Cryptanalysis of a system based on twisted reed–solomon codes,”Designs, Codes and Cryptography, vol. 88, no. 7, pp. 1285–1300, 2020

2020
[44]

On the structure of the schur squares of twisted generalized reed-solomon codes and application to cryptanalysis,

A. Couvreur, R. Pratihar, N. Tanısalı, and I. Zappatore, “On the structure of the schur squares of twisted generalized reed-solomon codes and application to cryptanalysis,” inInternational Conference on Post-Quantum Cryptography. Springer, 2025, pp. 3–34

2025
[45]

Algorithmic results in list decoding,

V . Guruswamiet al., “Algorithmic results in list decoding,”Foundations and Trends® in Theoretical Computer Science, vol. 2, no. 2, pp. 107–195, 2007

2007
[46]

Algebraic manipulation detection codes,

R. Cramer, S. Fehr, and C. Padr ´o, “Algebraic manipulation detection codes,”Science China Mathematics, vol. 56, no. 7, pp. 1349–1358, 2013

2013
[47]

Codes for computationally simple channels: Explicit constructions with optimal rate,

V . Guruswami and A. Smith, “Codes for computationally simple channels: Explicit constructions with optimal rate,” in2010 IEEE 51st Annual Symposium on Foundations of Computer Science. IEEE, 2010, pp. 723–732

2010
[48]

Fast modular transforms,

A. Borodin and R. Moenck, “Fast modular transforms,”Journal of Computer and System Sciences, vol. 8, no. 3, pp. 366–386, 1974

1974
[49]

The guruswami-sudan decoding algorithm for reed-solomon codes,

R. J. McEliece, “The guruswami-sudan decoding algorithm for reed-solomon codes,”IPN progress report, vol. 42, no. 153, 2003

2003

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [37]

Linear diophantine equations over polynomials and soft decoding of reed-solomon codes,

M. Alekhnovich, “Linear diophantine equations over polynomials and soft decoding of reed-solomon codes,” inThe 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.IEEE, 2002, pp. 439–448

2002

[2] [1]

New mds or near-mds self-dual codes,

T. A. Gulliver, J.-L. Kim, and Y . Lee, “New mds or near-mds self-dual codes,”IEEE transactions on information theory, vol. 54, no. 9, pp. 4354–4360, 2008

2008

[3] [2]

Construction of mds codes with complementary duals,

L. Jin, “Construction of mds codes with complementary duals,”IEEE Transactions on Information Theory, vol. 63, no. 5, pp. 2843–2847, 2016

2016

[4] [3]

New constructions of mds euclidean self-dual codes from grs codes and extended grs codes,

W. Fang and F.-W. Fu, “New constructions of mds euclidean self-dual codes from grs codes and extended grs codes,”IEEE Transactions on Information Theory, vol. 65, no. 9, pp. 5574–5579, 2019

2019

[5] [4]

New lcd mds codes constructed from generalized reed–solomon codes,

X. Shi, Q. Yue, and S. Yang, “New lcd mds codes constructed from generalized reed–solomon codes,”Journal of Algebra and Its Applications, vol. 18, no. 08, p. 1950150, 2019

2019

[6] [5]

Construction of mds self-dual codes from orthogonal matrices,

M. Shi, L. Sok, and P. Sol ´e, “Construction of mds self-dual codes from orthogonal matrices,”arXiv preprint arXiv:1610.07736, 2016

arXiv 2016

[7] [6]

Several classes of galois self-orthogonal mds codes and related applications,

Y . Li, Y . Su, S. Zhu, S. Li, and M. Shi, “Several classes of galois self-orthogonal mds codes and related applications,”Finite Fields and Their Applications, vol. 91, p. 102267, 2023

2023

[8] [7]

On insecurity of cryptosystems based on generalized reed-solomon codes,

V . M. Sidelnikov and S. O. Shestakov, “On insecurity of cryptosystems based on generalized reed-solomon codes,”Discrete Mathematics and Applications, vol. 2, no. 4, pp. 439–444, 1992

1992