{"id":"6e244f71-5754-41a1-b756-490beb6c74d7","arxiv_id":"2510.27012","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every unbounded-width CSP requires linearly many queries to test satisfiability in the bounded-degree oracle model; the paper reduces each such CSP from a hard linear-equation CSP over a finite abelian group.","lead":"An unbounded-width constraint satisfaction problem—one whose satisfiability cannot be decided by bounded local-consistency methods—cannot be tested with o(n) queries in the bounded-degree model. The result gives a single Ω(n) lower bound that covers 3-coloring, 3SAT, 3LIN, and hypergraph colorability, unifying a family of earlier ad-hoc lower bounds.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The unproven universal-algebra bridge (Theorem 3.2 via Appendix E) is the load-bearing step; the reduction's soundness depends entirely on it.","rationale":"The reader's weakest_assumption already identifies Lemma 3.4/Theorem 3.2, and I agree it is the most load-bearing. I scrutinized the rest: Lemma 5.4's expansion argument, the soundness counting, the reduction to cores, and the BOT02 generalization to arbitrary abelian groups are all internally consistent modulo standard details; the query-simulation in Lemma 5.7 is terse but can be formalized by fixing oracle orders. The only point where the paper relies on a nontrivial external result without a full proof is Theorem 3.2. Since the cited results are established, I do not think this warrants rejection; it is a verification gap rather than a demonstrated error. Hence UNCHANGED.","tokens_in":30985,"tokens_out":58007,"duration_ms":522601,"concrete_test":"Obtain the exact statements of [Val09, Prop 3.1] and [Sze92, Thm 6.1]. Check that [Val09] guarantees the strictly simple algebra is idempotent with the full polymorphism clone as signature, and that [Sze92, Thm 6.1] indeed classifies the unary-type case as operations compatible with an abelian group in Pol(3SumG). Then instantiate the chain for the two minimal nontrivial examples: the 2-element projection algebra (unary type) and the 3-element affine algebra over Z/3. For each, verify by enumerating the clones that the relations SG_b generated after adding constants match the statement of Lemma 3.4. If the classification or the generated relations fail in either example, Theorem 3.2 is false as used.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim reduces every unbounded-width CSP to linear equations over an abelian group G. This reduction requires Lemma 3.4, whose proof rests on Theorem 3.2. Theorem 3.2 is not proved in the paper; it is assembled in Appendix E from [BK14, Conjecture 4.3], [Val09, Prop 3.1], and [Sze92, Thm 6.1]. The delicate point is that the strictly simple idempotent algebra obtained by Valeriote's theorem must have operations compatible with an abelian group in such a way that they all belong to Pol(3SumG). This is automatic for affine-type algebras but non-obvious for unary-type algebras: an idempotent strictly simple unary-type algebra is essentially a projection algebra on a 2-element set, and the paper does not justify this classification or the resulting compatibility with a group structure. If the homomorphic image/subalgebra produced by Valeriote's theorem does not satisfy Cor E.4, then relations of the form (3.1) need not be generated by Γ∪ConstD, and the expander/soundness argument cannot be built. Because Appendix E only sketches the derivation and does not quote or re-prove the classification, this is the least secure point in the chain.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for every finite CSP template (D,Γ) of unbounded width, there are constants ε,d such that any ε-tester for satisfiability of CSP(Γ) in the bounded-degree model BD(d,n) must make Ω(n) queries. The proof combines the BOT02 linear-query lower bound for 3SUM-type linear equations with universal-algebraic results: it first shows (Lemma 3.4) that an unbounded-width repetition-closed template, after adding constant relations, can simulate ternary relations of the form φ(x1)+φ(x2)+φ(x3)=b over a finite abelian group; it then eliminates the constants by an expander gadget built from the Endomorphism relation of a core, and carries out the standard completeness/soundness/indistinguishability analysis. The claimed unification covers all previously known linear lower bounds for 3COL, 3SAT, 3LIN, and hypergraph colorability, and more generally all unbounded-width CSPs.","tokens_in":31226,"tokens_out":27528,"duration_ms":276816,"significance":"If the proof is correct, this is a strong and natural unification: it replaces case-by-case linear lower bounds with one theorem over the whole unbounded-width class, and it connects the property-testing question to the robust-satisfiability dichotomy of Dalmau–Krokhin and Barto–Kozik. The paper is well structured, gives careful statements of completeness and soundness, and includes appendices for the random-hypergraph lemmas and the Galois duality step. The main weakness is that the load-bearing bridge from unbounded width to linear equations (Theorem 3.2/Appendix E) is a sketch relying on a combination of deep universal-algebraic results, and several supporting lemmas in the appendices are stated or proved in a way that needs correction.","major_comments":[{"comment":"The reduction's central step is the claim that an unbounded-width core with idempotent polymorphism algebra has a homomorphic image of a subalgebra that is a strictly simple idempotent algebra of unary or affine type whose operations belong to Pol(3SumG). Appendix E derives this by citing [BK14], [Val09], and [Sze92] in sequence, but Corollary E.4 is asserted without a proof of the unary-type classification. The unary-type case is not obvious: it requires proving that the strictly simple unary-type algebra is term-equivalent to a projection algebra on a 2-element set (or otherwise affine over Z2) so that its operations preserve 3SumG. Since Lemma 3.4 is the bridge from unbounded width to the linear-equation hardness, this step needs either a precise quotation of the relevant classification theorem or a self-contained proof.","section":"§3 / Appendix E, Theorem 3.2 and Lemma 3.4"},{"comment":"As stated, item (2) is false. For d≥2, every vertex of [n]×[3] is incident to d hyperedges, one in each perfect matching M(i); therefore no total order of the full union ∪_i M(i) can have the property that every hyperedge has a vertex not appearing in any earlier hyperedge. The proof appears to intend the union of the hyperedges that are entirely contained in the chosen subset U (i.e., ∪_i M(i)[U]). The proposition must be restated and proved for that object. This proposition is used in the proof sketch of Lemma 4.7, so the indistinguishability of the base distributions is affected.","section":"Appendix D, Proposition D.2"},{"comment":"The inequality 1-(1-2ε)^D ≤ 1-2ε is incorrect for D>1. For example, with ε=0.01 and D=10, the left side is about 0.183, while the right side is 0.02. The expectation E_v[R((τ(v_x))_x)] is at most 1-(1-2ε)^D ≈ 2Dε, not 1-2ε. The subsequent martingale concentration argument can still be made to work by absorbing the factor D into the choice of ℓ, but as written the proof does not establish the claimed probability bound.","section":"Appendix D, proof of Lemma 5.4, Case 1"},{"comment":"The query-simulation argument is not fully rigorous. A query to a variable in Vconst or Vaux(1) can reveal a constraint belonging to the copy I_b of a particular original constraint C with right-hand side b; the identity of that copy depends on b, and the oracle on the original instance I may return a different constraint incident to the same original variable. The statement that such a query 'reveals no more information than a query to (j,1) in I' therefore needs a precise coupling or a query-by-query simulation. A constant-factor increase in the number of queries would be acceptable, but the lemma as stated assumes a one-to-one replacement and is not justified by the bullets given.","section":"§5.3, Lemma 5.7"}],"minor_comments":[{"comment":"Theorem 3.2 is attributed to [BK14], but Appendix E shows it is a combination of [BK14], [Val09], and [Sze92]. The citation should be adjusted so that the reader knows the statement is not literally one theorem of [BK14].","section":"References / §3"},{"comment":"There are several typos: 'reptition-closed' in §5.4, 'instace' in Lemma 5.6, 'assignemnt' in Appendix D, and 'support' is used before being defined. These are cosmetic but should be fixed.","section":"§5.4, Lemma 5.6, Appendix D"},{"comment":"The notation {R} for the repetition closure of a single relation is easy to confuse with the singleton set; a different symbol or a clarifying sentence would improve readability.","section":"§2.1 / Definition 2.3"},{"comment":"The appendix would benefit from stating the exact theorem of Szendrei used for the unary-type and affine-type cases, rather than only citing Theorem 6.1 in prose; this is related to the first major comment and would reduce the burden on the reader.","section":"Appendix E"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the black-box universal-algebra bridge in Appendix E: if Corollary E.4 is not fully justified, the entire reduction fails. The other issues in Appendix D and Lemma 5.7 appear repairable with local fixes, but they are load-bearing for indistinguishability and soundness. I would not accept the paper in its current form, but I believe the central approach is likely correct and worth a major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the main theorem is very likely right, and it's a genuinely useful unification. If you work on property testing of CSPs, this is the paper you want to cite for the unbounded-width Ω(n) lower bound. It absorbs the earlier ad-hoc lower bounds (3COL, 3SAT, 3LIN, hypergraph colorings) into one statement: every unbounded-width template is maximally hard to test in the bounded-degree model.\n\nWhat's actually new is the universal-algebraic bridge (Lemma 3.4) that turns any unbounded-width core template into relations that simulate linear equations over a finite abelian group, plus the reduction machinery — the expander gadget using the EndΓ relation, and the new random-regular-hypergraph lemma (Lemma 5.4) — that removes the need for constant relations. I read the completeness/soundness/indistinguishability chain in Section 5 carefully; the counting works and there's no hidden parameter fitting. The appendices include self-contained proofs of the Galois duality and the hypergraph concentration arguments, which is real evidence of care.\n\nThe soft spots are the expected ones. Theorem 3.2 is the load-bearing wall, and it is not proved in the paper. Appendix E is a sketch: unbounded width → variety admits unary/affine type (BK14) → a strictly simple idempotent homomorphic image of a subalgebra (Val09) → operations are affine over a group (Sze92). This is a chain of published results, but it relies on research-level universal algebra that most TCS readers won't know. The stress-test note worries that the unary-type case is not justified; I don't think that's where the risk is — idempotent strictly simple unary algebras are essentially projection algebras, and projections satisfy the affine identity over any group. The bigger risk is simply that the paper asks you to trust a lot of external machinery without re-deriving it. Also, the BOT02 lower bound for 3SumG over arbitrary abelian groups is asserted to follow by \"easy adaptation\" but no adaptation is given. That generalization is genuinely needed, since the group in Lemma 3.4 is arbitrary. It's almost certainly true, but it's unproven here. Minor: the BD* model is used without a formal definition.\n\nWho this is for: anyone working on property testing lower bounds, CSP dichotomy, or the query-to-streaming connection. It deserves a serious referee. My recommendation: send it to peer review, but ask the author to prove or precisely cite the abelian-group generalization of BOT02, and to expand the derivation of Theorem 3.2 enough that a nonexpert can check the chain. The result is significant and the proof is mostly there — it's a solid paper, not a house of cards.","headline":"The main theorem is very likely right and genuinely unifies the known linear lower bounds for CSP testing; the proof is careful, and the only real risk is the cited universal-algebraic black box.","tokens_in":31801,"tokens_out":4054,"would_cite":true,"duration_ms":42084,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that every constraint satisfaction problem of unbounded width requires Ω(n) queries to test satisfiability in the bounded-degree model, making such problems maximally hard to test and unifying all previously known linear lo","keywords":["property testing","bounded-degree model","constraint satisfaction problems","unbounded width","query lower bounds","MaxCSP","linear equations over abelian groups","universal algebra"],"falsifier":"Exhibit a repetition-closed core of unbounded width whose polymorphism algebra generates a variety admitting neither the unary nor the affine type; then the universal-algebraic simulation lemma fails. Alternatively, produce any ε-tester for a single unbounded-width CSP that makes o(n) queries, which would directly contradict Theorem 1.6.","tokens_in":30821,"feed_emoji":"🧩","tokens_out":4218,"duration_ms":42670,"temperature":0.7,"pith_summary":"This paper tries to establish that every constraint satisfaction problem (CSP) whose template has unbounded width is maximally hard to test in the bounded-degree query model: any tester that distinguishes satisfiable instances from instances far from satisfiable must read a linear number of variables. The result matters because it turns a scattered collection of linear lower bounds for specific problems like graph 3-coloring, 3SAT, and systems of linear equations into one theorem covering the entire unbounded-width class. The proof works by reducing the testing task for any unbounded-width CSP to testing equations of the form x+y+z=b over a finite abelian group, using universal-algebraic facts to justify the reduction and a random-regular-hypergraph gadget to enforce constant values. If correct, it says the only CSPs with any hope of sublinear testers are the bounded-width ones.","feed_headline":"Linear queries are unavoidable for testing unbounded-width CSPs","feed_subtitle":"One theorem unifies lower bounds for 3-coloring, 3SAT, and linear equations: any tester must read a constant fraction of variables.","key_machinery":"The hardness seed is the family of ternary sum relations 3SumG, defined by x+y+z=b over a finite abelian group G. The load-bearing bridge is the universal-algebraic lemma that every repetition-closed unbounded-width template, after adding constant relations, can generate lifted copies of these 3SumG relations on a subset D′ of its domain. The endomorphism relation EndΓ on the template provides a sub-unique relation, allowing a random regular hypergraph gadget to force variables to nearly constant values and thereby remove the added constants. Everything is measured in the bounded-degree query model, where the tester sees constraints incident to queried variables and distance is the number of","core_discovery":"The central claim is that width, a structural parameter measuring whether satisfiability can be certified by local consistency checks, draws the hardness line for testing satisfiability in the bounded-degree model: unbounded width forces Ω(n) queries. The proof's bridge is a lemma stating that any repetition-closed unbounded-width template, once constant relations are added, can generate ternary relations that behave exactly like x+y+z=b over a finite abelian group on a subset D′ of its domain. Since testing equations of that form is known to require linear queries, the paper builds a query-preserving reduction from those equations to the target CSP; a gadget built from an expander-like rand","pith_inferences":["Editorial inference: if the reduction here composes with the known phenomenological connection between bounded-degree query algorithms and multi-pass streaming (a connection the paper itself raises as a question), the linear-query lower bound may port to a linear-space lower bound for approximating MaxCSP on unbounded-width templates in streaming.","Editorial inference: the theorem suggests that query complexity of satisfiability testing is governed by bounded width alone, so the next quantitative question is the exact exponent for bounded-width templates — for example, whether 2COL's Θ(√n) behavior generalizes to all bounded-width cases or splits further.","Editorial inference: a concrete testable extension is whether the reduction can be made to show that the optimal soundness gap ε for a given template is computable from its polymorphism algebra; the paper leaves the analogous question for 3COL open.","Editorial inference: the proof's reliance on the universal-algebraic simulation lemma suggests that any attempt to build a sublinear tester for a bounded-width CSP should look for structure that provably excludes the affine or unary type in its polymorphism variety."],"forward_implications":["Every unbounded-width CSP template has an unconditional linear-query lower bound for testing satisfiability in the bounded-degree model, with no reliance on P vs NP.","All previously known linear lower bounds — for k-coloring of ℓ-uniform hypergraphs with (k,ℓ)≠(2,2), for 3SAT, and for systems of linear equations — become special cases of one theorem.","The same lower bound applies to the perfect-completeness MaxCSP problem, i.e., distinguishing value 1 from value at most 1−ε, on instances with Θ(n) constraints.","Bounded-width CSPs are left as the only remaining candidates for sublinear-query testers; the paper poses as an open problem whether all bounded-width templates actually admit such testers.","Because the lower bound is proved against sublinear-query algorithms, it does not follow from NP-hardness and is a strictly unconditional form of hardness in this model."],"fun_headline_variants":["Linear queries unavoidable for unbounded-width CSPs","Width is the wall: unbounded-width CSPs need Ω(n)","No sublinear testing for unbounded-width CSPs","Unbounded-width CSPs: linear queries or nothing"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The whole reduction depends on the lemma that any repetition-closed unbounded-width template, after adding constant relations, can generate ternary relations equivalent to x+y+z=b over some finite abelian group; the appendix only sketches the supporting universal-algebraic theorem, so if that bridge fails, the argument collapses.","fun_headline_variants_meta":{"raw":{"variants":["Linear queries unavoidable for unbounded-width CSPs","Width is the wall: unbounded-width CSPs need Ω(n)","No sublinear testing for unbounded-width CSPs","Unbounded-width CSPs: linear queries or nothing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000516,"raw_usage":{"total_tokens":2338,"prompt_tokens":738,"completion_tokens":1600,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":482,"completion_tokens_details":{"reasoning_tokens":1543}},"tokens_in":482,"tokens_out":1600,"duration_ms":12503,"temperature":1.0,"reasoning_tokens":1543,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T07:06:39.782946+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a repetition-closed core of unbounded width whose polymorphism algebra generates a variety admitting neither the unary nor the affine type; then the universal-algebraic simulation lemma fails. Alternatively, produce any ε-tester for a single unbounded-width CSP that makes o(n) queries, which would directly contradict Theorem 1.6.","supporting_citations":[],"review_version":1}