{"id":"f2ade100-bc64-4871-abc6-19e47dd900c4","arxiv_id":"2512.24217","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"Twisted GRS and Roth-Lempel codes can be list- and uniquely-decoded in near-linear time by running Guruswami-Sudan on a containing generalized Reed-Solomon code and filtering the output.","lead":"Researchers give new decoding algorithms for two families of non-standard error-correcting codes — twisted Reed-Solomon and Roth-Lempel codes — by treating them as subsets of standard Reed-Solomon codes and decoding the larger code first. The methods run in near-linear time under standard parameter conditions and include a probabilistic step that picks the true message from the candidate list with high probability.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Near-linear complexity is imported entirely from Alekhnovich's GS implementation (Theorem 1) with no proof or parameter-regime discussion; if that algorithm has a hidden n/k factor or rate condition, the fixed-rate near-linear claim collapses.","rationale":"The reader's weakest assumption matches the main load-bearing concern. The core reductions are sound: Lemma 4 correctly embeds P_TGRS(k,T) into F_q[x]<k', Theorem 2's filtering argument is exact, and Lemma 7's puncturing relation for Roth–Lempel codes is correct. The list-size and unique-decoding-radius arguments are internally consistent. However, the near-linear complexity claims are not independently established in this paper; they depend entirely on a cited external algorithm whose exact conditions are not discussed. This is not a question of internal inconsistency but of unsupported load-bearing premise. The paper would be conditional regardless of its presentation issue around O(n^2) twists versus near-linear runtime: the mathematical reductions deserve acceptance, but the complexity improvement should be verified against Alekhnovich's original theorem before being asserted as the paper's main gain. Hence the reader's CONDITIONAL verdict should remain unchanged.","tokens_in":20457,"tokens_out":25230,"duration_ms":238964,"concrete_test":"Consult Alekhnovich's FOCS 2002 paper and independently re-derive the exact complexity of Algorithm 1 in the regime k = Θ(n), s = O(1), and τ at the Johnson radius n − sqrt(nk(1+1/s)). Count field operations in both the interpolation and root-finding stages. If the total is O(n log^2 n log log n) in this regime, the fixed-rate near-linear claims of Theorems 3 and 8 stand; if either stage costs Θ(n^2) or contains a nonconstant factor in n/k, then the complexity section needs revision and the central complexity improvement does not follow from the cited work.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline complexity improvement—O(n log^2 n log log n) for fixed-rate TGRS and Roth–Lempel decoding—rests wholly on Theorem 1, which cites Alekhnovich [37] but gives no proof, no implementation, and no analysis of the algorithm's applicability to the parameter regimes used here. The critical regime is k' = Θ(n) for fixed-rate TGRS codes (and k = Θ(n) for RL codes), with fixed multiplicity s = O(1). Theorem 1 states the cost as O((s n/k)^{O(1)} n log^2 n log log n); this is constant only when n/k is constant and the hidden exponent is independent of k. If Alekhnovich's algorithm actually carries a factor like n/k, k log n, or requires a lower-bounded rate or special field size, then Section III.C's Theorem 3, Section V.C's Theorem 8, and the abstract's near-linear claim are unsupported. This is load-bearing because the GRS-supercode and puncturing reductions (Lemmas 4 and 7) are mathematically correct; the main novelty and improvement over the prior O(n^2) decoders is precisely the near-linear runtime, which is imported as a black box.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":20758,"tokens_out":24894,"duration_ms":221561,"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":[{"comment":"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.","section":"§III.C, Theorem 1 (also Theorems 3, 6, 8)"},{"comment":"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.","section":"§V.E, Theorem 10"},{"comment":"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.","section":"Abstract and §III.D (Remarks 1–2)"}],"minor_comments":[{"comment":"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 ...'.","section":"Theorems 2, 4, 5, 7"},{"comment":"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.","section":"§IV, Algorithm 5 and Theorem 5"},{"comment":"Table II appears garbled in the submitted text, with overlapping entries in the Guruswami-Sudan row. Please check the table formatting.","section":"Table II and general formatting"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid contribution with clean reductions and a fresh perspective on decoding non-GRS codes. The main concern is the unproven black-box complexity theorem; if the authors can provide an exact statement or proof of the Alekhnovich bound in the needed parameter regime, and fix the Theorem 10 parameter error, the paper is likely acceptable. I do not see any circularity or fitted-parameter issues."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThe 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.\n\nOne 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.\n\nOverall 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.","headline":"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.","tokens_in":21277,"tokens_out":2386,"would_cite":true,"duration_ms":24168,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B05","94B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Non-GRS MDS codes can be decoded near-linearly by embedding them in generalized Reed–Solomon codes and filtering the Guruswami–Sudan list.","keywords":["twisted generalized Reed–Solomon codes","Roth–Lempel codes","Guruswami–Sudan algorithm","list decoding","unique decoding","MDS codes","algebraic manipulation detection codes","near-linear decoding"],"falsifier":"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.","tokens_in":20312,"feed_emoji":"📡","tokens_out":9034,"duration_ms":74301,"temperature":0.7,"pith_summary":"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.","feed_headline":"Near-linear decoders found for two non-GRS code families","feed_subtitle":"Embedding into generalized Reed-Solomon codes unlocks list and unique decoding beyond half the distance.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Near-linear decoding for twisted GRS and Roth-Lempel codes","Decoders for twisted GRS and Roth-Lempel run near-linear","Beyond half-distance decoding for two non-GRS code families","First efficient decoder for Roth-Lempel, near-linear for twisted GRS"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Near-linear decoding for twisted GRS and Roth-Lempel codes","Decoders for twisted GRS and Roth-Lempel run near-linear","Beyond half-distance decoding for two non-GRS code families","First efficient decoder for Roth-Lempel, near-linear for twisted GRS"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0007,"raw_usage":{"total_tokens":3056,"prompt_tokens":861,"completion_tokens":2195,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":605,"completion_tokens_details":{"reasoning_tokens":2122}},"tokens_in":605,"tokens_out":2195,"duration_ms":13772,"temperature":1.0,"reasoning_tokens":2122,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T13:25:55.019173+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}