{"id":"9e6be6b5-b5ce-4c17-8ce5-d94da0d03ec1","arxiv_id":"2611.16333","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The weighted, nonuniform fault-tolerant matroid basis problem is fixed-parameter tractable on oracle and linear matroids, while explicit-scenario versions become W[1]-hard by rank plus scenario size.","lead":"This paper gives fast fixed-parameter algorithms for finding minimum-cost matroid bases that survive element failures, answering open questions about weighted costs and safe-versus-vulnerable element splits. It also draws the tractability boundary for explicitly listed failure scenarios, including a new W[1]-hardness result.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"Polynomial-certificate nonvanishing over small finite fields may fail because the formal polynomial GP can be nonzero yet vanish under every evaluation of the remaining indeterminates, breaking the compression guarantee of Lemma 10.","rationale":"The reader identified the polynomial-certificate nonvanishing as the weakest assumption, but focused on the possibility that a nonzero formal polynomial could vanish at every evaluation over a small finite field. The reader's concern was that the nonvanishing test might fail over small finite fields, but they did not fully articulate the specific gap: that the compression lemma uses formal nonvanishing after substitution, but feasibility requires actual nonvanishing under some evaluation of the remaining indeterminates. The paper acknowledges the distinction between formal and numerical nonvanishing, but does not address how the compression step bridges this gap. The reader's verdict was CONDITIONAL, suggesting they thought the issue could be resolved with additional verification. However, I believe this is a more fundamental issue: the compression argument as presented does not guarantee that the retained partial selection is actually feasible, because the formal nonvanishing of evZ(GP) does not imply that there exists an evaluation of the remaining variables that makes it nonzero. The algorithm never evaluates those variables, so it cannot distinguish between a polynomial that is nonzero but vanishes everywhere and one that has a nonzero evaluation. This is a load-bearing gap that would require a significant modification to the argument, such as working over an infinite field or using a different certificate that avoids this issue. Therefore, I recommend REJECT unless the authors can provide a rigorous justification that formal nonvanishing suffices for feasibility in this context.","tokens_in":33326,"tokens_out":980,"duration_ms":221052,"concrete_test":"Construct a concrete example over F_2 with small parameters (e.g., r=2, k=1, a simple linear matroid) where the polynomial certificate GP is nonzero but evZ(GP) is a nonzero polynomial in F_2[Tj, uj] that vanishes at every assignment (e.g., a polynomial like T_1^2 - T_1). Check whether the algorithm would incorrectly retain a partial selection P' that is not actually feasible with any completion Z. If such an example exists, the compression guarantee fails.","verdict_should_be":"REJECT","load_bearing_attack":"The polynomial certificate GP in Section 4.3 is a formal polynomial in the ring Rp,q = F[Xh,ℓ, Tj]. Lemma 10 compresses partial selections by retaining a linear basis of coefficient vectors in a fixed monomial basis. The compression guarantee relies on the following: for a fixed completion Z, the substitution evZ is an F-linear map from the coefficient space to the target polynomial ring F[Tj, uj], and if evZ(GP) ≠ 0 (as a formal polynomial) then P∪Z is feasible. However, the target ring after substitution still contains the tag indeterminates Tj and the auxiliary uj. The test for feasibility is whether evZ(GP) is not identically zero as a polynomial in those remaining variables. Over a finite field F, a nonzero polynomial can vanish at every assignment of its variables (e.g., x^q - x over F_q). The paper acknowledges this distinction (\"Formal nonvanishing is distinguished from nonvanishing after numerical evaluation, particularly over finite fields.\") but the compression argument in Lemma 10 only guarantees that evZ(GP') ≠ 0 as a formal polynomial. It does not guarantee that there exists an actual evaluation of the remaining indeterminates that makes it nonzero, which would be needed to conclude that P'∪Z is feasible. The algorithm never evaluates these indeterminates; it only checks formal nonvanishing of GP at the final step when q=0 (so no remaining variables). But during the dynamic program, the compression step uses the formal nonvanishing condition to retain representatives. If evZ(GP) is nonzero as a formal polynomial but vanishes under every evaluation, then the implication \"evZ(GP) ≠ 0 ⇒ P∪Z feasible\" is false, because feasibility is a property of actual field elements, not of formal polynomials.","agreement_with_reader":"partial"},"referee_report":null,"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"This paper does what it says on the tin: it resolves the two weighted/nonuniform open questions from Bentert et al. and gives a clean hardness boundary for explicit scenarios. The main technical novelty is the polynomial-certificate compression in Section 4.3, which is genuinely new and not just a routine application of representative families. The flat-avoidance lemma (Lemma 5) is also a nice combinatorial construction that may find other uses.\n\nThe proofs are coherent. I checked the load-bearing steps: the layered sparsification, the cocircuit-counting induction, the flat-avoidance replacement, the determinant nonvanishing in the polynomial certificate, and both hardness reductions. They all hold up. The paper is well-organized and the writing is clear.\n\nThe stress-test concern about formal nonvanishing over small finite fields does not land. The algorithm never evaluates the remaining indeterminates; it only checks formal nonvanishing at the final step when q=0 (so no remaining variables). During the DP, the compression uses the formal condition to retain representatives, which is valid because the substitution map is linear and the implication 'ev_Z(GP) ≠ 0 ⇒ P∪Z feasible' is proven via Lemma 8's Cauchy-Binet expansion, which is a formal polynomial identity over any integral domain. The paper explicitly acknowledges the distinction between formal nonvanishing and evaluation. So the stress-test is a misunderstanding of the proof structure.\n\nSoft spots: (1) The polynomial-certificate machinery is dense and would benefit from a more detailed exposition or a worked example. (2) The W[1]-hardness result was developed with AI assistance; the authors say they verified it independently, but I would want a human to double-check the reduction carefully. (3) The running-time bounds are not optimized and the paper does not claim they are tight, but the exponents are large enough that the algorithms are primarily of theoretical interest.\n\nWho this is for: researchers in parameterized matroid optimization. It deserves a serious referee. I would accept a review invitation for this paper.\n\nRecommendation: accept after minor revision. The main results are correct and the techniques are interesting. The authors should expand the exposition of Section 4.3 and add a note about independent verification of the AI-assisted hardness result.","headline":"Resolves two open questions from Bentert et al. with clean new constructions; the polynomial-certificate compression is the real technical meat, and it holds up on close reading.","tokens_in":34313,"tokens_out":691,"duration_ms":8318},"pith_extraction":null,"created_at":"2026-11-13T06:48:32.213188+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":null,"supporting_citations":[],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}