{"id":"fd785a8e-51ff-4dad-b59a-dc832e6f794f","arxiv_id":"2504.10399","paper_version":3,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Develops near-linear time unique decoders for IRS, FRS, and multiplicity codes under a new semi-adversarial error model that achieve information-theoretic optimal performance.","lead":"This paper introduces a semi-adversarial error model mixing adversarial corruptions with random symbol replacements and gives near-linear time unique decoding algorithms for interleaved Reed-Solomon, folded Reed-Solomon, and multiplicity codes that match the information-theoretic optimum. A smart generalist might read it to see how coding theory can handle realistic mixed-error channels more efficiently than pure random or adversarial models alone.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Monomial-tracking bounds for semi-adversarial mixtures rest on unstated independence assumptions between random and adversarial symbols","rationale":"The reader's identification of the monomial-tracking and interpolation steps as the weakest assumption is accurate; the full text would need to contain an explicit handling of adaptive adversaries or a reduction showing that non-adaptive mixtures suffice. Until that step is verified, the optimality and runtime claims remain conditional on the analysis surviving this correlation issue. No other internal inconsistency is visible from the abstract and high-level description.","tokens_in":1806,"tokens_out":371,"duration_ms":31318,"concrete_test":"Extract the precise probability statement in the IRS analysis (likely the main theorem on monomial tracking); instantiate a small field (q=2^8) and block length n=64 with exactly k adversarial positions chosen adversarially after the random symbols are fixed; run the decoder 10^4 times and check whether the observed success rate stays within 5% of the claimed bound. Deviation larger than that indicates the independence assumption fails.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim requires that the monomial-tracking analysis (used for IRS and extended via new interpolations to FRS/multiplicity codes) correctly upper-bounds the failure probability when an arbitrary subset of symbols is replaced by adversarial values while the remainder are uniform random. The technique appears to track degree distributions or leading terms during interpolation, but the provided description does not specify whether the adversary is allowed to choose its symbols after seeing the random ones or the codeword, which would correlate the error locations and potentially invalidate the probabilistic counting arguments that deliver the information-theoretic optimum and near-linear runtime. If those correlations are not controlled, the claimed success for “most mixtures” may hold only for weaker adversarial models.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper introduces the semi-adversarial error model, where an arbitrary subset of codeword symbols may be corrupted by an adversary while the remainder are replaced by uniformly random symbols. It presents near-linear-time unique decoding algorithms for interleaved Reed-Solomon (IRS) codes by refining the Bleichenbacher-Kiayias-Yung (BKY) algorithm with a novel monomial-tracking technique, and extends the approach to folded Reed-Solomon (FRS) and univariate multiplicity codes via new interpolation procedures that replace the root-finding step of prior algorithms (e.g., Guruswami-Wang) with polynomial long division. The analyses are claimed to achieve the information-theoretic optimum for most mixtures of random and adversarial errors.","tokens_in":1965,"tokens_out":602,"duration_ms":70321,"significance":"If the monomial-tracking arguments are shown to be rigorous, the work supplies the first efficient unique decoders that interpolate between fully random and fully adversarial regimes for these code families, with a concrete simplification (long division in place of root-finding) that may be of independent interest. The explicit matching to information-theoretic bounds and the constructive use of the BKY and Guruswami-Wang frameworks are strengths.","major_comments":[{"comment":"IRS decoder analysis (monomial-tracking section): the probabilistic counting arguments that deliver the information-theoretic optimum must explicitly address whether the adversary may select its symbols after observing the random symbols and the codeword; if adaptive choice is permitted, the claimed independence between random and adversarial positions used to bound the failure probability requires a separate justification or counter-example, as correlations could invalidate the degree-distribution tracking.","section":"IRS monomial-tracking analysis"},{"comment":"FRS and multiplicity-code extensions: the claim that the new interpolations yield near-linear runtime while preserving optimality rests on 'more robust monomial-tracking arguments' than for IRS; however, the manuscript provides no explicit comparison of the resulting error-probability bounds to those of Guruswami-Wang, nor a parameter-range verification that the long-division step does not increase the failure probability beyond the stated optimum.","section":"FRS and multiplicity extensions"}],"minor_comments":[{"comment":"Notation for the semi-adversarial parameter (fraction of adversarial symbols) should be introduced once and used consistently; currently it appears under multiple symbols in the abstract and main text.","section":"Notation"},{"comment":"The manuscript would benefit from a short table summarizing the achieved rate-error trade-offs for each code family under the semi-adversarial model.","section":"Results summary"}],"recommendation":"major_revision","confidential_remarks":"The semi-adversarial model appears novel in the stated form, but the authors should confirm it is not subsumed by existing hybrid or partially random error models in the literature; otherwise the positioning of the contribution could be adjusted."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and insightful comments on our manuscript. We address the two major comments point by point below, clarifying the error model and outlining planned revisions to strengthen the presentation.","responses":[{"response":"We thank the referee for highlighting this subtlety. The semi-adversarial error model in the paper defines the adversary as selecting an arbitrary subset of positions to corrupt arbitrarily, with the remaining positions replaced by uniformly random symbols chosen independently of both the codeword and the adversary's choices. This is a non-adaptive model in which the random symbols are generated without the adversary observing them in advance. Consequently, the independence between random and adversarial positions holds, and the monomial-tracking arguments for bounding the failure probability remain valid. We will add an explicit clarification of the non-adaptive nature of the adversary in the revised manuscript.","revision_made":"yes","referee_comment":"[IRS monomial-tracking analysis] IRS decoder analysis (monomial-tracking section): the probabilistic counting arguments that deliver the information-theoretic optimum must explicitly address whether the adversary may select its symbols after observing the random symbols and the codeword; if adaptive choice is permitted, the claimed independence between random and adversarial positions used to bound the failure probability requires a separate justification or counter-example, as correlations could invalidate the degree-distribution tracking."},{"response":"We appreciate the referee's suggestion for greater explicitness. Although the monomial-tracking arguments for FRS and multiplicity codes are designed to be more robust to accommodate the folded and multiplicity structures, the manuscript does not provide a direct side-by-side comparison of the resulting error-probability bounds against the Guruswami-Wang algorithm, nor a parameter-range check confirming that the long-division step preserves the stated optimality. In the revision we will add such a comparison and verification that the long-division replacement does not increase the failure probability beyond the information-theoretic optimum in the relevant regimes.","revision_made":"yes","referee_comment":"[FRS and multiplicity extensions] FRS and multiplicity-code extensions: the claim that the new interpolations yield near-linear runtime while preserving optimality rests on 'more robust monomial-tracking arguments' than for IRS; however, the manuscript provides no explicit comparison of the resulting error-probability bounds to those of Guruswami-Wang, nor a parameter-range verification that the long-division step does not increase the failure probability beyond the stated optimum."}],"tokens_in":1498,"tokens_out":509,"duration_ms":42213,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main point is that they define semi-adversarial errors as a mix of random and adversarial corruptions, then build near-linear time unique decoders for interleaved Reed-Solomon, folded Reed-Solomon, and univariate multiplicity codes that reach the optimal radius for most mixtures. The monomial-tracking technique lets them analyze the BKY algorithm in this setting for IRS, and they adapt the same idea to FRS and multiplicity codes by swapping root-finding for simple polynomial long division. That change is a concrete simplification over Guruswami-Wang style methods. The work sits squarely on prior BKY and Guruswami-Wang results, so the foundations are clear and the extensions are the actual addition. If the analysis is tight, the result is useful for any setting where errors split between noise and targeted jamming. The soft spot is the handling of possible correlations. The monomial-tracking bounds rely on probabilistic counting that assumes the random and adversarial symbols behave independently enough for the degree distributions to work out. If the adversary can pick its symbols after seeing the random ones or the codeword, those counts could shift and the claimed optimality for “most mixtures” would only hold under a non-adaptive adversary. The paper needs to state this assumption explicitly and show the bounds survive it. Runtime claims for the full parameter ranges also want direct verification. This is for coding theorists who care about efficient algebraic decoders and hybrid error models. A reader working on list or unique decoding algorithms would get concrete constructions and a new analysis trick to look at. It deserves peer review because the claims are specific enough to check and the techniques are grounded in existing frameworks.","headline":"The paper introduces a semi-adversarial error model and gives near-linear unique decoders for IRS, FRS, and multiplicity codes that claim to match information-theoretic bounds, with monomial tracking as the main new tool.","tokens_in":2478,"tokens_out":414,"would_cite":false,"duration_ms":32174,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[{"relation":"unclear","rs_module":"IndisputableMonolith/Cost/FunctionalEquation.lean","rs_theorem":"washburn_uniqueness_aczel","paper_passage":"We use a novel monomial-tracking technique to analyze its performance in this new semi-adversarial errors... Bounding Matrix Rank: Proof of Theorem 3.6"},{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/ArithmeticFromLogic.lean","rs_theorem":"embed_injective","paper_passage":"the block matrix B ... has full column rank"}],"headline":"Coding-theoretic monomial tracking and matrix-rank analysis for semi-adversarial RS decoding","alignment":"orthogonal","rationale":"The paper develops near-linear-time unique decoders for interleaved/folded RS and multiplicity codes under a hybrid error model by reducing correctness to full-column-rank of certain block-Vandermonde matrices and exhibiting unique monomials in their symbolic determinants. These are standard algebraic-combinatorial arguments in coding theory; they invoke neither J-cost functionals, ratio-symmetric costs, golden-ratio ladders, 8-tick periodicity, nor any parameter-free derivation of physical constants. The RS framework therefore neither confirms nor contradicts any claim in the paper.","tokens_in":63771,"confidence":"high","tokens_out":298,"duration_ms":11809,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Near-linear time unique decoding works for Reed-Solomon codes under semi-adversarial errors","keywords":["Reed-Solomon codes","unique decoding","semi-adversarial errors","interleaved Reed-Solomon","folded Reed-Solomon","multiplicity codes","near-linear time"],"falsifier":"An explicit semi-adversarial error pattern below the information-theoretic threshold on which the decoder fails to recover the correct message would disprove the claimed performance and optimality.","tokens_in":2702,"feed_emoji":"🔍","tokens_out":654,"duration_ms":64999,"temperature":0.7,"pith_summary":"The paper defines semi-adversarial errors as a setting where an adversary corrupts some code symbols while the remaining errors are uniformly random. It constructs near-linear time unique decoders for interleaved Reed-Solomon codes by refining an existing random-error algorithm through a monomial-tracking analysis. The same framework yields fast algorithms for folded Reed-Solomon and univariate multiplicity codes by introducing interpolations that replace root-finding steps with direct polynomial division. These decoders achieve the information-theoretic optimum across most mixtures of the two error types.","feed_headline":"Decoders fix mixed random and adversarial errors in Reed-Solomon codes","feed_subtitle":"Near-linear time algorithms reach the information-theoretic limit for most error mixtures across these code families.","key_machinery":"Monomial-tracking technique that bounds decoder success when some symbols are chosen adversarially and the rest are random, together with new interpolations that enable polynomial long division in place of root finding.","core_discovery":"For interleaved Reed-Solomon codes an improved version of the Bleichenbacher-Kiayias-Yung decoder, equipped with a novel monomial-tracking technique, performs unique decoding in near-linear time for most semi-adversarial error patterns. Novel interpolations extend the approach to folded Reed-Solomon and univariate multiplicity codes, replacing the root-finding step of prior algorithms with straightforward polynomial long division while preserving the same near-linear runtime and matching the information-theoretic optimum.","pith_inferences":["The monomial-tracking method may apply to other algebraic codes whose decoders track coefficient growth.","Systems facing hybrid random-plus-adversarial noise could adopt these decoders for efficiency without sacrificing optimality.","Parameter regimes where the random fraction dominates may admit even simpler implementations."],"forward_implications":["Interleaved Reed-Solomon codes admit near-linear unique decoding against most semi-adversarial mixtures via monomial tracking.","Folded Reed-Solomon codes admit near-linear unique decoding via interpolations that reduce to polynomial division.","Univariate multiplicity codes admit near-linear unique decoding under the same mixed error model.","All three families achieve the information-theoretic optimum for the semi-adversarial setting.","The new techniques simplify traditional decoding pipelines while retaining optimal error correction."],"fun_headline_variants":["Unique decoding algorithms for Reed-Solomon codes under semi-adversarial errors","Decoding Reed-Solomon codes with mixed random and adversarial errors","Near-linear decoding for semi-adversarial errors in Reed-Solomon code families","Unique decoding for interleaved and folded Reed-Solomon codes with mixed errors","Decoding algorithms for semi-adversarial errors in Reed-Solomon and multiplicity codes mat"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The monomial-tracking analysis and new interpolations accurately predict decoder success on error patterns that mix adversarial and random corruptions.","fun_headline_variants_meta":{"raw":{"variants":["Unique decoding algorithms for Reed-Solomon codes under semi-adversarial errors","Decoding Reed-Solomon codes with mixed random and adversarial errors","Near-linear decoding for semi-adversarial errors in Reed-Solomon code families","Unique decoding for interleaved and folded Reed-Solomon codes with mixed errors","Decoding algorithms for semi-adversarial errors in Reed-Solomon and multiplicity codes match optimum"]},"model":"grok-4.3","cost_usd":0.01559,"raw_usage":{"total_tokens":6629,"prompt_tokens":732,"num_sources_used":0,"completion_tokens":93,"cost_in_usd_ticks":155903000,"prompt_tokens_details":{"text_tokens":732,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":5804,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":732,"tokens_out":93,"duration_ms":75884,"temperature":1.0,"reasoning_tokens":5804,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-22T19:53:52.363803+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit semi-adversarial error pattern below the information-theoretic threshold on which the decoder fails to recover the correct message would disprove the claimed performance and optimality.","supporting_citations":[],"review_version":1}