{"id":"93b10266-849f-4a77-a07e-80e3c22ef603","arxiv_id":"2607.06852","paper_version":1,"verdict":"ACCEPT","confidence":"UNKNOWN","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"An FPT-time O(2^k log n)-approximation is given for k-MMSA_3, alongside gap-preserving reductions clarifying inapproximability across the MMSA hierarchy.","lead":"This paper gives an algorithm and hardness results for a parameterized version of finding minimal satisfying assignments for monotone Boolean circuits. It clarifies where approximation difficulty spikes across a hierarchy of circuit depths, relevant to theoretical computer science and complexity theory.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified; Lemma 2.4 pruning is sound and the reduction's soundness argument is correct.","rationale":"The reader correctly identified the pruning step (Lemma 2.4) as the structural linchpin of Theorem 4.1, but the concern that pruning could alter satisfiability does not actually land: the proof shows that weight-≤k assignments cannot satisfy conjunctions of size >k, so removing them is safe for completeness, and C' ≤ C ensures soundness. The argument is self-contained and correct. The three main contributions — the O(2^k log n) approximation (Theorem 3.1), the gap-preserving reduction (Theorem 4.1), and the sharpened MMSA_4 inapproximability (Corollaries 5.6–5.7) — are each verified by straightforward combinatorial arguments with no hidden assumptions. The paper's positioning of MMSA_3 as 'close to MMSA_2' in the FPT regime is well-supported by both the algorithm and the reduction. No verdict adjustment is warranted.","tokens_in":13343,"tokens_out":701,"duration_ms":876115,"concrete_test":"Independently verify the completeness direction of Theorem 4.1 on a concrete small example: construct a k-MMSA_3 instance with k=2, n=4, where the optimal satisfying assignment has weight 2, and at least two distinct bottom conjunctions are subsets of the optimal support. Confirm that the reduced MMSA_2 instance has OPT ≤ 2^k = 4, and that the soundness decoding of any weight-(h/k) MMSA_2 solution yields an MMSA_3 solution of weight ≤ h. This exercises the injective mapping f and the union bound on set sizes simultaneously.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest_assumption flags Lemma 2.4's pruning step as potentially load-bearing, suggesting that if a satisfying assignment requires a conjunction of size > k, pruning could alter satisfiability. However, the proof of Lemma 2.4 is internally sound: if OPT(C) ≤ k, any satisfying assignment x has weight ≤ k, so no bottom conjunction with |N_{i,j}| > k can be satisfied (it would require more than k variables set to 1). Thus removing such conjunctions preserves all weight-≤k satisfying assignments. For soundness, C' ≤ C pointwise, so SAT(C') ⊆ SAT(C), meaning OPT(C') ≥ OPT(C) and gaps are preserved. The reduction in Theorem 4.1 correctly applies this pruning before contracting bottom conjunctions into MMSA_2 variables. The completeness argument (at most 2^k true conjunctions) and soundness argument (decoded assignment has weight ≤ k·|A| ≤ h) are both valid. The algorithm in Theorem 3.1 is a clean greedy covering argument with a correct averaging bound. The MMSA_4 results (Corollaries 5.6, 5.7) follow from a straightforward reparameterization of Marx's reduction with perfect hash families of size h = n^{Θ(1/k)}. No internal inconsistency or hidden assumption was found in any of the three main results.","agreement_with_reader":"disagree"},"referee_report":{"model":"glm-5.2","summary":"This paper studies the parameterized approximability of the Minimum Monotone Satisfying Assignment (MMSA) hierarchy, focusing on the third level, k-MMSA_3, which sits between k-SetCover (k-MMSA_2) and k-MinLabel (captured by k-MMSA_4). The authors make three main contributions: (1) a deterministic FPT-time O(2^k log n)-approximation algorithm for k-MMSA_3 (Theorem 3.1), showing that in the parameterized regime the third level remains close to the second; (2) an FPT-time gap-preserving reduction from (k,h)-gap k-MMSA_3 to (2k, h/k)-gap k-MMSA_2 (Theorem 4.1), establishing that stronger inapproximability for k-MMSA_3 would imply new hardness for k-SetCover; (3) improved inapproximability for k-MMSA_4 by revisiting Marx's reduction with better parameters, yielding no n^{o(1)}-factor FPT approximation under W[2]≠FPT (Corollary 5.7) and no n^{O(1/k)}-factor approximation in n^{o(k)} time under ETH (Corollary 5.6). The proofs are clean, self-contained, and build on standard tools (perfect hash families, greedy covering, padding arguments).","tokens_in":13720,"tokens_out":1409,"duration_ms":1138109,"significance":"The paper addresses a well-motivated gap in the parameterized complexity of the MMSA hierarchy. The O(2^k log n)-approximation for k-MMSA_3 is a concrete algorithmic result showing the third level is not dramatically harder than k-SetCover in the FPT regime, contrasting with the polynomial-time setting where MMSA_3 is known to be much harder. The gap-preserving reduction from k-MMSA_3 to k-MMSA_2 is conceptually valuable: it explains why k-MMSA_3 has not yielded independent inapproximability and provides a potential route to resolving open problems for k-SetCover. The improved k-MMSA_4 inapproximability, obtained by a careful reparameterization of Marx's existing reduction, cleanly separates the third and fourth levels. The results are falsifiable in the standard sense of complexity-theoretic conditional lower bounds, and the algorithmic upper bound is constructive and implementable in principle. The paper ships no machine-checked proofs or code, but the proofs are short enough to be verified by hand.","major_comments":[],"minor_comments":[{"comment":"§1, paragraph 2: The footnote 1 notes that [DS04] studied monotone formulae rather than circuits, and that the distinction matters only in the unbounded-depth setting. It would help the reader to clarify in the main text (not just the footnote) that all results in this paper concern the circuit variant, since the W[P]/W[SAT] discussion later in the same paragraph refers to the unbounded-depth setting.","section":null},{"comment":"§1, paragraph 5: The phrase 'total-FPT-inapproximability' is defined in footnote 4 as ruling out FPT-time f(k)-approximation for every computable f. This terminology is slightly non-standard; consider citing or aligning with the terminology used in [Mar13] or [FKLM20] for consistency.","section":null},{"comment":"§2.2, Definition 2.3: The circuit form uses w_{i_1,...,i_t} as an index in [n], but the notation is introduced without explicitly stating that multiple tuples (i_1,...,i_t) can map to the same index (i.e., the same variable can appear in multiple bottom gates). This is implicit but worth stating for clarity.","section":null},{"comment":"§3, proof of Theorem 3.1: The algorithm enumerates at most n^2 candidate sets N_{a,b} per iteration. It would be useful to state the total running time explicitly as O(2^k · log n · poly(n)), or more precisely O(2^k · log n · n^2 · poly(n)), to make the FPT claim fully transparent.","section":null},{"comment":"§4, proof of Theorem 4.1: The reduction outputs a k-MMSA_2 instance on at most n^2 variables. Corollary 4.2 then states the contrapositive in terms of t(√n, log k). The substitution n → n^2 and k → 2k is correct, but the step from t(n^2, 2k) · 2^k to t(√n, log k)/k in the denominator could benefit from one line of algebraic explanation, as the direction of the implication is easy to get backwards.","section":null},{"comment":"§5.2, Theorem 5.4: The reduction constructs C' by adding two outer layers. The statement says 'the same n variables,' but the perfect hash family introduces indices i ∈ [m] and T ∈ (Σ choose k) that index the outer conjunction and disjunction. It would be clearer to state that the new circuit is on the same set of input variables but has additional gates indexed by [m] × (Σ choose k).","section":null},{"comment":"Table 1: The entry for k-MMSA_4 'n^{1/poly(k)}' under ETH with 'n^{o(k)}' runtime is listed with reference [KLM19, KN21], while the improved 'n^{O(1/k)}' result from Corollary 5.6 is listed separately. Consider merging these into a single row or adding a note that the latter supersedes the former, to avoid the impression that both are the best known.","section":null},{"comment":"References: The arXiv identifier in the header (2607.06852) suggests a 2026 submission, but several references (e.g., [LRSW23], [CMV23]) are from 2023. This is not an error per se, but the authors should verify that no more recent results have appeared that would affect the discussion of k-SetCover inapproximability in §1.","section":null}],"recommendation":"accept","confidential_remarks":"The paper is a solid contribution to parameterized approximation complexity. The three results are individually modest but collectively paint a coherent picture of where the MMSA hierarchy transitions from polylogarithmic to polynomial inapproximability. The reduction from k-MMSA_3 to k-MMSA_2 is the most interesting conceptual contribution, as it provides a concrete framework for future hardness transfer. I see no reason to delay publication; the minor comments are purely presentational."},"author_rebuttal":null,"desk_editor":{"model":"glm-5.2","letter":"The main thing to know: this paper pins down the parameterized approximability of k-MMSA_3 and clarifies where the hierarchy gets hard. Three results: an O(2^k log n) FPT approximation for k-MMSA_3, a gap-preserving reduction from (k,h)-gap MMSA_3 to (2k, h/k)-gap MMSA_2, and sharpened inapproximability for k-MMSA_4 (n^{o(1)} under W[2]≠FPT, n^{O(1/k)} in n^{o(k)} time under ETH). The upshot is that level 3 stays close to level 2 in the FPT regime, while level 4 is where poly(n) inapproximability kicks in. That separation is the real conceptual contribution. The algorithm is clean. The key observation is that a weight-k satisfying assignment has at most 2^k distinct subsets, so a greedy covering argument over bottom conjunctions gives geometric decrease with ratio 1 - 1/2^k per step, terminating in O(2^k log n) iterations. Nothing fancy, but it works and it's deterministic. The reduction from MMSA_3 to MMSA_2 is the more interesting structural piece. It contracts each distinct bottom conjunction into a single MMSA_2 variable. Completeness: at most 2^k true conjunctions. Soundness: decoding a weight-(h/k) MMSA_2 solution back gives weight at most h for MMSA_3. The pruning lemma (2.4) that lets you discard bottom conjunctions of size > k is sound — any weight-k assignment cannot satisfy those anyway, and C' ≤ C pointwise preserves gaps. The stress-test concern about this was a non-issue on reading. The MMSA_4 results are the least novel piece. They come from plugging better parameters (h = n^{Θ(1/k)} via perfect hash families) into Marx's existing reduction. The improvement from f(k) to n^{o(1)} under W[2]≠FPT and from n^{1/poly(k)} to n^{O(1/k)} under ETH is real but incremental. The paper is honest about this being a reparameterization rather than a new technique. One thing I'd push on if refereeing: the reduction from MMSA_3 to MMSA_2 blows up the variable count to n^2, so the corollary about transferring lower bounds has a square-root in it. The authors state this correctly (Corollary 4.2), but it does weaken the implications somewhat — a log(n) lower bound for MMSA_3 would give log(n) for MMSA_2, but the constant factors and the 2^k factor in the gap mean you need fairly strong MMSA_3 hardness to get anything new for SetCover. Overall: solid, correct, well-written. The algorithm and reduction are new and clean. The MMSA_4 results are a nice cleanup. Deserves a serious referee.","headline":"Clean FPT approximation for k-MMSA_3 plus a gap-preserving reduction to k-MMSA_2; MMSA_4 lower bounds sharpened via better parameters for Marx's reduction.","tokens_in":14265,"tokens_out":729,"would_cite":true,"duration_ms":114093,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Level 3 of MMSA stays close to Set Cover in FPT regime","keywords":[],"falsifier":"A weight-k satisfying assignment of the original circuit that relies on a bottom conjunction of size greater than k being true—but this is impossible by definition, since setting more than k variables to 1 exceeds the weight budget. The pruning is therefore safe for the promise version of the problem.","tokens_in":13624,"feed_emoji":"🔧","tokens_out":1346,"duration_ms":191916,"temperature":0.7,"pith_summary":"The paper studies a hierarchy of optimization problems called Minimum Monotone Satisfying Assignment (MMSA), defined by how many times a Boolean circuit alternates between AND and OR gates. The second level is equivalent to Set Cover, where parameterized inapproximability is relatively mild (polylogarithmic in n). The fourth level is known to be much harder, admitting polynomial-factor inapproximability. The third level, sitting between these two, had remained unexplored in the parameterized setting. This paper shows that the third level is surprisingly close to the second: there is a fixed-parameter tractable algorithm achieving an O(2^k log n)-approximation, nearly matching the O(log n) greedy ratio for Set Cover. The key mechanism is a greedy covering argument that exploits the fact that any weight-k solution has at most 2^k distinct subsets, so enumerating candidate bottom-level conjunctions guarantees a constant fraction of progress per step. Complementing this, the paper gives a gap-preserving reduction from the third level to the second level, meaning that any strong inapproximability for the third level would automatically yield new lower bounds for Set Cover itself. The paper also sharpens known hardness for the fourth level by revisiting an earlier gap-creating reduction with better-chosen parameters, showing n^{o(1)} inapproximability under W[2]≠FPT and n^{O(1/k)} inapproximability in n^{o(k)} time under ETH. Together these results locate where the complexity jump occurs in the MMSA hierarchy: between the third and fourth levels, not between the second and third.","feed_headline":"Level 3 of MMSA stays close to Set Cover in FPT regime","feed_subtitle":"O(2^k log n)-approximation for depth-3 monotone circuits, plus a reduction that could transfer hardness down to Set Cover","key_machinery":"The approximation algorithm uses a greedy covering strategy on the top-level AND clauses of the MMSA_3 circuit. After pruning bottom conjunctions to size at most k (justified because a weight-k assignment cannot satisfy any larger conjunction), the algorithm repeatedly selects the bottom conjunction covering the most currently uncovered clauses. The analysis bounds progress via a counting argument: a weight-k solution's support has at most 2^k distinct subsets, so some subset must serve as a witness for at least a 1/2^k fraction of uncovered clauses. The gap-preserving reduction from MMSA_3 to MMSA_2 contracts each distinct bottom conjunction into a single Boolean variable, mapping a weight-","core_discovery":"The central discovery is that parameterized MMSA at depth 3 admits an O(2^k log n)-approximation in FPT time, placing it in the same qualitative regime as Set Cover (depth 2) rather than depth 4. The approximation works by a greedy set-cover-style argument: since any weight-k satisfying assignment has at most 2^k distinct subsets of its support, and each bottom conjunction in the circuit has size at most k, one can always find a conjunction that covers at least a 1/2^k fraction of currently uncovered top-level clauses, yielding termination in O(2^k log n) steps. The paper also provides a reduction in the reverse direction—from gap MMSA_3 to gap MMSA_2—establishing that depth-3 hardness would","pith_inferences":["The reduction from MMSA_3 to MMSA_2 suggests a possible research program: construct MMSA_3 gap instances directly (e.g., via PCP or label-cover techniques adapted to the parameterized setting) and then transfer the resulting hardness down to Set Cover, bypassing the barriers that have stalled direct approaches.","The 2^k factor in the approximation ratio may not be tight; if one could improve it to poly(k) or even polylog(k), the reduction would imply correspondingly stronger consequences for Set Cover, potentially matching known lower bounds.","The fact that MMSA_3 and MMSA_2 are close in approximability but MMSA_4 is far suggests that the alternation from depth 3 to depth 4 introduces a qualitative change in the combinatorial structure—possibly related to the transition from set-cover-type to label-cover-type constraints."],"forward_implications":["A polylogarithmic or even constant-factor FPT inapproximability for MMSA_3 under W[1]≠FPT would imply the same for k-SetCover, resolving a major open problem.","An ω(2^k) FPT inapproximability for MMSA_3 under W[2]≠FPT would yield superconstant FPT inapproximability for Set Cover, another long-standing open question.","The separation between MMSA_3 (approximable within O(2^k log n)) and MMSA_4 (inapproximable within n^{o(1)}) clarifies that the complexity jump in the MMSA hierarchy occurs specifically between depths 3 and 4 in the parameterized regime.","The improved ETH-based lower bound for MMSA_4 (n^{O(1/k)} in n^{o(k)} time) strengthens the known connection between MMSA_4 and k-MinLabel, suggesting depth-4 MMSA as the canonical hard problem for polynomial-factor parameterized inapproximability."],"fun_headline_variants":["Depth-3 MMSA matches Set Cover in FPT approximation","FPT algorithm places depth-3 MMSA in Set Cover regime","MMSA depth 3 stays close to Set Cover under FPT","O(2^k log n) FPT approximation for depth-3 MMSA","Depth-3 MMSA approximability separates from depth 4"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The pruning step (Lemma 2.4) removes every bottom conjunction of size greater than k from the MMSA_3 circuit, justified by the observation that no weight-k assignment can satisfy such a conjunction. This is sound for the gap problem where the yes-case promises a solution of weight at most k, but it means the reduction and algorithm are tailored to the parameterized promise setting and do not directly apply to the unparameterized optimization version.","fun_headline_variants_meta":{"raw":{"variants":["Depth-3 MMSA matches Set Cover in FPT approximation","FPT algorithm places depth-3 MMSA in Set Cover regime","MMSA depth 3 stays close to Set Cover under FPT","O(2^k log n) FPT approximation for depth-3 MMSA","Depth-3 MMSA approximability separates from depth 4"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":961,"prompt_tokens":879,"completion_tokens":82,"prompt_tokens_details":null},"tokens_in":879,"tokens_out":82,"duration_ms":24902,"temperature":1.0,"reasoning_tokens":null,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T00:11:10.399523+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"A weight-k satisfying assignment of the original circuit that relies on a bottom conjunction of size greater than k being true—but this is impossible by definition, since setting more than k variables to 1 exceeds the weight budget. The pruning is therefore safe for the promise version of the problem.","supporting_citations":[],"review_version":1}