{"id":"cf60fcff-95e4-43e7-a0f3-f2d2a2d9a000","arxiv_id":"2507.08693","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Minimum-cost CSPs admit a |D|-approximation for dual-discriminator languages, require near-unanimity polymorphisms for any constant-factor approximation, and have an exact approximability dichotomy over permutation-closed languages.","lead":"The paper analyzes minimum-cost constraint satisfaction problems, where every way of choosing a value for a variable has a price and the goal is the cheapest assignment that satisfies all constraints. It proves new approximation algorithms, a general necessary condition for any constant-factor approximation, and a complete classification for languages with all permutation relations, and it shows a published dichotomy claim fails under the Unique Games Conjecture.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The unbounded-width hardness proof rests on a first-power pp-interpretation theorem (Thm 4.6) that is stronger than the standard bounded-width characterization; if it should be 'some power', the cost-preserving reduction in Lemma 4.5 breaks and Thm 1.2's necessity of NU does not follow.","rationale":"I read the full manuscript in good faith. The algorithmic side (Theorem 1.1) is well supported: the greedy charging argument and the LP-based rounding are self-contained and the critical (2,3)-minimality preservation step in Theorem 3.12 is correct. The bounded-width hardness case (Lemma 4.14) is a clean adaptation of DKM18 and rests on standard hypergraph vertex cover hardness. The Min UnCut gadget (Theorem 4.20) is exact and correctly demonstrates that NU does not suffice under UGC. The single most load-bearing assumption is the exact form of Theorem 4.6 in the unbounded-width case. The proof of Lemma 4.12 requires a first-power pp-interpretation of the affine relations over a group. The cost-preserving reduction (Lemma 4.5) genuinely depends on n=1: for n≥2 there is no natural way to split a variable's label cost across an n-tuple of variables while preserving the optimum, and the authors acknowledge this. If Theorem 4.6 only holds for arbitrary powers (the standard formulation of the bounded-width collapse involves pp-constructions with powering), then the reduction from Nearest Codeword fails and Theorem 1.2's unbounded-width half is not proved. This does not mean the theorem is false—my own spot-checks on 3-coloring, NAE, near-projection, and switching clones all admit first-power affine interpretations—but the discrepancy between 'first power' and the standard 'some power' makes this the point where the proof could break. The reader identified exactly this as the weakest assumption, and I agree. Given the paper is otherwise careful and self-aware, the appropriate action is to make acceptance conditional on a verification of Theorem 4.6's first-power form (or a replacement argument).","tokens_in":22474,"tokens_out":43231,"duration_ms":498993,"concrete_test":"Verify Theorem 4.6 against the primary sources: extract the exact statement of the bounded-width characterization in Barto–Kozik (JACM 2014) and Dalmau–Krokhin (TOCT 2013) and check whether they assert 'in the first power' or only an interpretation/pp-construction using a power n≥1. As an independent analytical check, attempt to prove Lemma 4.5 (cost-preserving reduction) for a 2-power pp-interpretation by assigning costs to pairs; the authors' note suggests this is impossible, and a concrete failed attempt would confirm that the first-power condition is indispensable. If the sources only give a power-n statement, construct or identify a bounded-width-less language whose affine type is witnessed only on A^k (k>1), which would falsify Theorem 4.6 as stated.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central hardness result (Theorem 1.2) splits into a bounded-width and an unbounded-width case. The unbounded-width case (Lemma 4.12) needs a cost-preserving reduction from MinCostCSP over affine relations to MinCostCSP(Γ). This reduction is supplied by Lemma 4.5, which works only for pp-interpretations in the first power: replacing a variable by an n-tuple (n≥2) does not admit a natural translation of the variable-label cost function, as the authors themselves note. Consequently, Lemma 4.12 relies entirely on Theorem 4.6, which asserts that every Γ without bounded width pp-interprets the affine relations Γ(G) of a nontrivial finite abelian group in the first power, using pp-definitions without equality. This exact form is not the standard bounded-width characterization: the usual statements (Barto–Kozik 2014; Dalmau–Krokhin 2013) guarantee a pp-interpretation or pp-construction with powering (n≥1), where the affine type may appear on a subset of A^k for k>1. If Theorem 4.6 is an overstatement and only a power-n interpretation is guaranteed, then the cost cannot be transported, and the Nearest Codeword hardness does not transfer to MinCostCSP(Γ). Thus the necessity of a conservative NU polymorphism for constant-factor approximability is not established by this argument. This is the single load-bearing link in the hardness chain; the algorithmic and gadget parts (Sections 3 and 4.3) are sound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the constant-factor approximability of minimum cost constraint satisfaction problems (MinCostCSP) through the universal-algebraic lens. It proves that if a constraint language has the dual discriminator operation as a polymorphism, then MinCostCSP is |D|-approximable in polynomial time; it gives two algorithms, one greedy and one based on the basic LP relaxation. Complementarily, it proves that any language admitting a constant-factor approximation must have a conservative near-unanimity polymorphism unless P = NP, yielding a dichotomy for languages containing all permutation relations. It also gives a UGC-based example of a language with a majority polymorphism that is nonetheless hard to approximate within any constant factor.","tokens_in":22616,"tokens_out":41340,"duration_ms":483806,"significance":"If the results are correct, they substantially advance the algebraic theory of constant-factor approximability for MinCostCSP, extending the DKM18 necessity result for MinCSP and providing a clean dichotomy for a natural generalization of Boolean CSPs with variable negation. The algorithmic part is elegant: the greedy charging argument in Theorem 3.11 and the LP threshold argument in Theorem 3.12 are self-contained and sound. The hardness arguments are reductions from Nearest Codeword and hypergraph vertex cover, following the DKM18 framework. The paper is proof-based, with no fitting parameters, and the main claims are falsifiable in the usual sense. The principal caveat is the precise provenance of the first-power pp-interpretation theorem used in the unbounded-width hardness case.","major_comments":[{"comment":"The unbounded-width half of the proof of Theorem 1.2 rests entirely on Theorem 4.6, which asserts that every language without bounded width pp-interprets the affine relations of a nontrivial finite abelian group in the first power, using pp-definitions without equality. This exact first-power, equality-free formulation is load-bearing: as the authors themselves note in Section 4.1, cost translation in Lemma 4.5 is straightforward only for n = 1, and there is no natural translation for n ≥ 2. The cited sources [BK14, DK13] are not pinpointed to a specific theorem or page, and the bounded-width characterization is often stated in the literature in terms of pp-constructions or pp-interpretations with powering. Please supply the precise theorem statement and location in [BK14, DK13], or a proof of the first-power claim. If only a power-n version is available, then Lemma 4.12 does not go through, and the necessity of a conservative near-unanimity polymorphism for constant-factor approximability is not established by the argument as written.","section":"§4.2, Theorem 4.6 and Lemma 4.12"}],"minor_comments":[{"comment":"In the proof of Lemma 4.5, the sentence 'so we add (the constraints and the auxiliary variables of) this instance to I2' should refer to I1, not I2.","section":"§4.1, Lemma 4.5 proof"},{"comment":"The text refers to 'Schaffer [Sch78]'; the reference is to Thomas J. Schaefer, so the name should be spelled 'Schaefer'.","section":"§1, Introduction"},{"comment":"There are several typographical slips: 'pp-interpretes' should be 'pp-interprets', 'Barto el al.' should be 'Barto et al.', and 'condtion' should be 'condition'.","section":"§4.1 and §4.2"},{"comment":"The notation 'tend' in Observations 3.7 and 3.8 is informal; please use a clearer notation such as t_end or t^end to denote the final values of t.","section":"§3.2, Algorithm 1"},{"comment":"Even if the first-power statement is correct, Theorem 4.6 should carry a precise citation to a numbered theorem in [BK14] or [DK13], since the formulation is unusually specific and is central to the hardness proof.","section":"§4.2, Theorem 4.6"}],"recommendation":"major_revision","confidential_remarks":"The central issue is purely the verification of Theorem 4.6. If the authors can pinpoint the exact first-power statement in the cited literature, or provide a proof, the paper is very strong. I found no problems with the greedy or LP algorithms, and the rest of the hardness chain appears sound. My recommendation is driven by the need to resolve this one load-bearing point before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The algorithmic half is solid, and the hardness half is one citation away from solid. The greedy and LP algorithms for dual-discriminator languages (Theorem 1.1) are genuinely new, and the charging analysis checks out. The dichotomy for permutation-closed languages (Theorem 1.3) is a nice application of Marchenkov/Szendrei, and the hard predicate P_H with a conservative majority polymorphism (Theorem 4.20) is a clean gadget that usefully contradicts a published claim.\n\nThe soft spot is the unbounded-width case of Theorem 1.2. The proof of Lemma 4.12 depends entirely on Theorem 4.6, which says that a language without bounded width pp-interprets the affine relations of a nontrivial finite abelian group in the first power, without equality. That is stronger than the standard bounded-width characterizations I know from Barto–Kozik and Dalmau–Krokhin, which typically give pp-constructions or pp-interpretations in some power n ≥ 1. The authors themselves note that cost transport breaks for n ≥ 2. So if Theorem 4.6 is only true up to powering, the Nearest Codeword reduction does not transfer, and the necessity of a conservative NU polymorphism is not established by this argument. The paper does not prove Theorem 4.6; it cites it. This is a load-bearing gap, not a cosmetic one.\n\nElsewhere the paper is careful: it explicitly conditions hardness on P ≠ NP and UGC, it states the contradiction with [RRS19] transparently, and it lets infinite costs simulate unary constraints. The |D| ≤ 4 exception handling in Section 5 is cited rather than proved, which is minor. My guess is that the main theorems are correct, and the fix is either a proof of the first-power theorem or a cost-preserving reduction that survives powering. But a referee needs to resolve this before acceptance.\n\nThe paper deserves a serious referee. I would take it to a reading group, and I would cite it for the algorithmic results and the P_H example even while the hardness proof has an open thread.","headline":"Strong algorithms and a crisp dichotomy, but the unbounded-width hardness leans on a first-power pp-interpretation citation I couldn't confirm.","tokens_in":23377,"tokens_out":35193,"would_cite":true,"duration_ms":379591,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68W25","08A70"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that MinCostCSP(Γ) is polynomial-time |D|-approximable whenever the dual discriminator preserves Γ, and that any constant-factor approximation forces a near-unanimity polymorphism unless P = NP.","keywords":["minimum cost CSP","constant-factor approximation","polymorphism","near-unanimity operation","dual discriminator","bounded width","homogeneous algebras","Unique Games Conjecture"],"falsifier":"Run Algorithm 1 or Algorithm 2 on a small, explicitly listed MinCostCSP instance whose language is preserved by the dual discriminator and check whether the returned solution costs more than |D| times the optimum; finding such an instance would refute Theorem 1.1, while exhibiting a polynomial-time constant-factor approximation for any language without a conservative near-unanimity polymorphism would refute Theorem 1.2 unless P = NP.","tokens_in":22072,"feed_emoji":"🧩","tokens_out":10365,"duration_ms":106384,"temperature":0.7,"pith_summary":"MinCostCSP is the optimisation problem of assigning values to variables so that a given set of constraints is satisfied while minimising a per-variable, per-label cost. This paper claims that the constant-factor approximability of MinCostCSP over a fixed constraint language is governed by the algebra of its polymorphisms: with a dual discriminator operation, a |D|-approximation is always achievable in polynomial time; without a conservative near-unanimity operation, no constant-factor approximation exists unless P = NP. These results meet for languages that contain all permutation relations, yielding a full dichotomy: |D|-approximable if a conservative majority polymorphism exists, NP-hard to approximate within any constant factor otherwise. The paper also gives a constrained example showing that, assuming the Unique Games Conjecture, a majority polymorphism alone does not guarantee approximability in general.","feed_headline":"MinCostCSP approximability turns on one polymorphism","feed_subtitle":"Constraint languages with a near-unanimity polymorphism are |D|-approximable; without one, no constant factor unless P=NP.","key_machinery":"The machinery is the polymorphism clone of Γ, studied through two named operations. The dual discriminator d(x,y,z) returns the majority value among x, y, z when the three are not all distinct, and the first argument otherwise; it is a majority operation, so any language it preserves is 2-decomposable (Theorem 2.10 from [JCC98]), letting the algorithms work with binary (2,3)-minimal instances in which every two-variable partial assignment extends to a third variable. Binary relations preserved by d then have the restricted 0/1/all shapes of Lemma 3.3—products, cross-like unions, and bijective matchings—which is exactly what makes the greedy fixing step and the LP rounding preserve (2,3)-minimality. The hardness side runs on pp-interpretations in the first power, the gadget translation that allows costs of a MinCostCSP instance to be carried into another MinCostCSP instance; the bounded-width characterization [BK14, DK13] says an unbounded-width language first-power pp-interprets affine equations over some finite abelian group, enabling the Nearest Codeword reduction, while without an NU operation a pp-defined relation supplies the hypergraph vertex cover reduction [DGKR05, DKM18].","core_discovery":"The central claim is a pair of bracketing results. On the algorithmic side, if a finite-domain constraint language Γ is preserved by the dual discriminator operation—the ternary operation that returns the majority label when a majority exists and otherwise the first argument—then every satisfiable MinCostCSP(Γ) instance admits a polynomial-time |D|-approximation, via either a greedy algorithm that fixes variables one at a time and pays at most |D| times the per-iteration optimum, or an LP-rounding algorithm based on the basic linear programming relaxation that discards labels of LP probability below 1/|D|. On the hardness side, if MinCostCSP(Γ) has any constant-factor approximation, then Pol(Γ) must contain a conservative near-unanimity operation, unless P = NP: unbounded-width languages reduce from Nearest Codeword through a first-power pp-interpretation of affine equations over a finite abelian group, while bounded-width languages without an NU polymorphism reduce from k-uniform hypergraph vertex cover. For languages containing all permutation relations the two sides close into a dichotomy (Theorem 1.3). A separate construction, a ternary relation with a conservative majority polymorphism whose MinCostCSP reduces from Min UnCut, shows that the NU condition alone is not sufficient under the Unique Games Conjecture.","pith_inferences":["Editorial extension: the first-power cost-transfer lemma suggests a general recipe for proving inapproximability of other optimization CSPs: any language that first-power pp-interprets an NP-hard MinCostCSP inherits its approximation hardness, so locating first-power interpretations, rather than general ones, may be the right target for future hardness results.","Editorial extension: the LP algorithm's threshold 1/|D| is tailored to the dual discriminator; a natural testable conjecture is that for k-ary near-unanimity languages, a similar threshold-based rounding of the basic LP yields a factor depending on D and k, possibly improving the |D| bound for specific languages.","Editorial extension: because Theorem 4.20 relies on UGC and only rules out sufficient-NU under that conjecture, an unconditional proof for P_H, or a demonstration that the same hardness follows from a weaker assumption, would sharpen the boundary; conversely, a refutation of UGC would leave open whether there is a larger tractable class.","Editorial extension: the paper's combination of Marchenkov's classification with approximation suggests that other clone classifications, for example of homogeneous or conservative clones, may translate directly into approximation dichotomies for MinCostCSP over restricted relation sets."],"forward_implications":["In the Boolean domain (|D| = 2), the necessary NU condition is also sufficient, so the paper recovers the Khanna et al. classification of constant-factor approximable MinCostCSPs as 2CNF-definable or IHB languages (Remark 4.15).","For any language containing all permutation relations, deciding whether MinCostCSP(Γ) is |D|-approximable reduces to checking whether Pol(Γ) contains a conservative majority operation; otherwise the problem is inapproximable within any constant factor unless P = NP.","The greedy algorithm's cost-accounting argument implies the |D| ratio holds for every satisfiable input, not merely for instances whose optimum is large, because the bound compares directly with the true optimum.","The UGC-based P_H example means that a complete dichotomy for all languages over domains of size at least 3 cannot stop at the NU test; it must single out a proper subclass of near-unanimity languages."],"supporting_citations":[{"why":"Supplies the (2,3)-minimality framework and the theorem that nontrivial bounded-width instances are satisfiable in polynomial time, on which both algorithms rely.","marker":"[Bar14]"},{"why":"Part of the bounded-width characterization (Theorem 4.6) that drives the unbounded-width hardness case.","marker":"[BK14]"},{"why":"Completes the bounded-width characterization used to pp-interpret affine relations over a finite abelian group in the first power.","marker":"[DK13]"},{"why":"Supplies the bounded-width hardness lemma (pp-defining the hypergraph vertex cover relation without NU) and the overall template for the NU necessity proof.","marker":"[DKM18]"},{"why":"Gives the theorem that languages preserved by a (k+1)-ary NU operation are k-decomposable, letting the algorithms assume binary constraints.","marker":"[JCC98]"},{"why":"Establishes that Nearest Codeword over any finite field is hard to approximate within 2^{log^{1-eps} n}, the source of the unbounded-width hardness.","marker":"[DMS03]"},{"why":"Establishes that k-uniform hypergraph vertex cover is NP-hard to approximate within k-1-eps, the source of the bounded-width hardness.","marker":"[DGKR05]"},{"why":"Gives the UGC-based Min UnCut hardness that the P_H counterexample reduces from.","marker":"[KKMO07]"},{"why":"Classifies homogeneous algebras, the backbone of the dichotomy for languages containing all permutation relations.","marker":"[Mar82]"},{"why":"Provides the clone classification theorem (Theorem 5.7) through which Marchenkov's classification is applied to constraint languages.","marker":"[Sze86]"}],"fun_headline_variants":["MinCostCSP approximation hinges on near-unanimity","Dual discriminator gives |D|-approximation for MinCostCSP","Near-unanimity polymorphism decides MinCostCSP approximability","No NU polymorphism means no constant-factor approximation","Constant-factor approximability of MinCostCSP collapses to a single operation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"All cost-transferring hardness reductions in the paper depend on the cited result that an unbounded-width language can simulate affine relations over a finite abelian group with one domain element per encoded element; if some unbounded-width language needed several elements per encoded element, the known cost translation would break and the constant-factor hardness conclusion for that language would no longer follow from this argument.","fun_headline_variants_meta":{"raw":{"variants":["MinCostCSP approximation hinges on near-unanimity","Dual discriminator gives |D|-approximation for MinCostCSP","Near-unanimity polymorphism decides MinCostCSP approximability","No NU polymorphism means no constant-factor approximation","Constant-factor approximability of MinCostCSP collapses to a single operation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000677,"raw_usage":{"total_tokens":3129,"prompt_tokens":1046,"completion_tokens":2083,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":662,"completion_tokens_details":{"reasoning_tokens":1997}},"tokens_in":662,"tokens_out":2083,"duration_ms":15545,"temperature":1.0,"reasoning_tokens":1997,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T18:18:56.063810+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 or Algorithm 2 on a small, explicitly listed MinCostCSP instance whose language is preserved by the dual discriminator and check whether the returned solution costs more than |D| times the optimum; finding such an instance would refute Theorem 1.1, while exhibiting a polynomial-time constant-factor approximation for any language without a conservative near-unanimity polymorphism would refute Theorem 1.2 unless P = NP.","supporting_citations":[],"review_version":1}