{"id":"06e9228e-349f-4cf1-adf1-ce9f17e7f29b","arxiv_id":"2601.22691","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"CSPs over FO expansions of finitely bounded homogeneous model-complete cores are either FO-definable (in non-uniform AC0) or L-hard under FO reductions.","lead":"The paper proves that constraint satisfaction problems over first-order expansions of finitely bounded homogeneous model-complete cores are either first-order definable (hence in non-uniform AC0) or L-hard under first-order reductions. This is the broadest such dichotomy result to date within the open Bodirsky-Pinsker conjecture.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"Generalization step from finite Larose-Tesson proof to infinite homogeneous structures may embed unverified assumptions on reducts and model-complete cores","rationale":"The reader's weakest assumption directly identifies the generalization step as the load-bearing point. Because the paper supplies a new finite proof and then claims a direct lift, verifying that no extra infinitary assumptions are used is the single concrete check that would either confirm or refute the claim.","tokens_in":1664,"tokens_out":336,"duration_ms":13719,"concrete_test":"Extract the subsection that states the infinite generalization (likely §4 or §5). Re-derive the key lemma that transfers the finite dichotomy to the infinite setting, substituting only the model-complete-core and finite-boundedness hypotheses; if any identity or case distinction requires an additional property not implied by those hypotheses, the lift is incomplete.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim requires that the new finite proof lifts verbatim once the input is restricted to first-order expansions of finitely bounded homogeneous model-complete cores. The finite proof presumably uses finiteness to control the possible polymorphisms or to obtain a finite number of cases for the dichotomy; the infinite case must therefore invoke homogeneity and finite boundedness to recover an analogous finiteness or compactness argument. If any step in the lift silently relies on the reduct being a core in a stronger sense than model-completeness (e.g., that every endomorphism is an automorphism, or that the age is finitely bounded in a way that preserves the relevant identities), the dichotomy could fail for some reducts that satisfy the stated hypotheses but not the hidden ones.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper proves that CSPs over first-order expansions of finitely bounded homogeneous model-complete cores are either first-order definable (hence in non-uniform AC^0) or L-hard under first-order reductions. The argument proceeds by first supplying a new proof of the Larose-Tesson theorem for finite structures and then generalizing that proof to the infinite case using homogeneity and finite boundedness.","tokens_in":1816,"tokens_out":344,"duration_ms":23296,"significance":"If the generalization holds, the result supplies the broadest known complexity dichotomy inside the scope of the Bodirsky-Pinsker conjecture, linking FO definability directly to non-uniform AC^0 and establishing L-hardness under FO reductions for the complementary case. The new finite proof and its explicit lift constitute a reusable technical contribution that may accelerate further progress on the full conjecture.","major_comments":[{"comment":"The central generalization step (from the new finite Larose-Tesson proof to infinite homogeneous structures) must explicitly identify which arguments in the finite case rely on finiteness (e.g., enumeration of polymorphisms or exhaustive case analysis) and show how homogeneity plus finite boundedness of the age substitute for them; without this identification the lift risks hidden assumptions on the reducts beyond model-completeness.","section":"Generalization from finite to infinite case"}],"minor_comments":[{"comment":"The abstract and introduction should include a brief pointer to the precise statement of the Larose-Tesson theorem being reproved, for readers unfamiliar with the finite-domain literature.","section":"Introduction"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive assessment of the result and its significance within the Bodirsky-Pinsker conjecture, as well as for the constructive major comment. We address the point below and agree to strengthen the exposition of the generalization.","responses":[{"response":"We agree that an explicit identification will improve clarity. Our new proof of the Larose-Tesson theorem (Section 3) deliberately avoids enumeration of polymorphisms and exhaustive case analysis; it instead reduces to the model-complete core via a direct construction of a witnessing polymorphism from the assumption that the CSP is not FO-definable, using finiteness only to guarantee that the core exists and that the domain is finite for the AC0 upper bound. The generalization (Section 4) substitutes homogeneity for finiteness by invoking the Fraïssé limit property that every finite substructure embeds into the homogeneous structure, allowing the same polymorphism to be lifted uniformly; finite boundedness of the age replaces exhaustive search by ensuring only finitely many minimal forbidden substructures exist, which bounds the local configurations that must be considered. We will revise by inserting a dedicated paragraph at the start of Section 4 that maps each step of the finite proof to its infinite counterpart and states precisely where homogeneity and finite boundedness substitute for finiteness.","revision_made":"yes","referee_comment":"[Generalization from finite to infinite case] The central generalization step (from the new finite Larose-Tesson proof to infinite homogeneous structures) must explicitly identify which arguments in the finite case rely on finiteness (e.g., enumeration of polymorphisms or exhaustive case analysis) and show how homogeneity plus finite boundedness of the age substitute for them; without this identification the lift risks hidden assumptions on the reducts beyond model-completeness."}],"tokens_in":1235,"tokens_out":378,"duration_ms":32428,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The headline result is that CSPs over those infinite structures are either first-order definable (hence in non-uniform AC0) or L-hard under first-order reductions. They reach it by first reproving the finite Larose-Tesson theorem and then generalizing the argument using homogeneity and finite boundedness. That combination is new and it does organize a noticeably larger slice of the Bodirsky-Pinsker landscape than earlier partial dichotomies. The strategy is stated plainly and the finite proof is presented as potentially reusable on its own. That is the useful part. The soft spot is the generalization step itself. The abstract does not show how the finite argument survives the move to infinite structures; homogeneity and model-completeness are invoked, but it is not clear whether they fully replace the finiteness that controlled polymorphisms or case distinctions in the original proof. If some reducts satisfy the stated hypotheses yet fail an unstated condition on endomorphisms or ages, the dichotomy could have gaps. Without the full write-up it is impossible to tell how tight the argument is. This is for people already working on infinite-domain CSPs and the Bodirsky-Pinsker conjecture. A reader who wants the current broadest known dichotomy in that area will find the claim worth checking. I would send it to referees. The scope is large enough and the approach looks straightforward enough that a careful review can settle whether the lift holds.","headline":"The paper gives a new proof of Larose-Tesson for finite structures and extends the dichotomy to first-order expansions of finitely bounded homogeneous model-complete cores, but the lift to the infinite case is the part that still needs verification.","tokens_in":2327,"tokens_out":370,"would_cite":false,"duration_ms":19797,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"CSP dichotomy over homogeneous structures uses model theory and minimality algorithms with no RS overlap","alignment":"orthogonal","rationale":"Paper proves FO vs L-hard dichotomy for first-order expansions of finitely bounded homogeneous model-complete cores by generalizing a new proof of Larose-Tesson theorem; machinery centers on A-formulae, (k,ℓ)-minimality, balanced implications, finite duality, and obstructions. RS framework (reality_from_one_distinction, Jcost uniqueness via Aczél, φ-ladder constants, 8-tick/D=3 forcing in AlexanderDuality) derives spacetime and constants from a single distinction with zero adjustable parameters; no shared cost functions, ratio symmetry, periodicity, or parameter-free constant derivations appear.","tokens_in":62466,"confidence":"high","tokens_out":169,"duration_ms":9793,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"CSPs over first-order expansions of finitely bounded homogeneous model-complete cores are either first-order definable or L-hard under first-order reduction.","keywords":["constraint satisfaction problems","dichotomy theorem","first-order definable","L-hard","homogeneous structures","model-complete cores","infinite domains","Bodirsky-Pinsker conjecture"],"falsifier":"A concrete first-order expansion of a finitely bounded homogeneous model-complete core whose CSP is solvable in deterministic logarithmic space yet not first-order definable would falsify the claimed dichotomy.","tokens_in":2554,"feed_emoji":"⚖️","tokens_out":650,"duration_ms":30667,"temperature":0.7,"pith_summary":"The paper establishes a complexity dichotomy for constraint satisfaction problems on first-order expansions of finitely bounded homogeneous model-complete cores. These CSPs are either first-order definable, and therefore lie in non-uniform AC0, or they are hard for logarithmic space under first-order reductions. The argument begins with a new proof of the Larose-Tesson theorem for finite structures and then lifts the same reasoning to the infinite setting, covering a wide portion of the structures appearing in the open Bodirsky-Pinsker conjecture.","feed_headline":"Infinite CSPs split into FO-definable or L-hard","feed_subtitle":"First-order expansions of finitely bounded homogeneous model-complete cores fall into AC0 or logarithmic-space hard cases.","key_machinery":"A new proof of the Larose-Tesson theorem, first obtained for finite structures and then lifted to infinite structures, that separates the CSPs into first-order definable versus L-hard cases.","core_discovery":"CSPs over first-order expansions of finitely bounded homogeneous model-complete cores are either first-order definable and hence in non-uniform AC0 or L-hard under first-order reduction. The proof proceeds by first establishing a new proof of the Larose-Tesson theorem for finite structures and then generalizing that argument to the infinite case.","pith_inferences":["The lifting technique may extend to other descriptive-complexity classifications that currently separate finite and infinite cases.","Concrete homogeneous structures such as the random graph or the rational order can now be placed on one side or the other of the dichotomy by checking the model-complete-core condition.","If the full Bodirsky-Pinsker conjecture holds, the present result would imply that all remaining NP-complete cases lie outside the model-complete-core class."],"forward_implications":["No CSP in this class can have complexity strictly between first-order logic and L.","The dichotomy applies uniformly to every first-order expansion of any such core.","The tractable cases admit non-uniform AC0 decision procedures.","The result supplies the broadest complexity classification known for structures inside the Bodirsky-Pinsker conjecture."],"fun_headline_variants":["CSPs over bounded homogeneous cores: FO or L-hard","First-order expansions split CSPs into AC0 or L-hard","Generalized Larose-Tesson: infinite CSPs FO or L-hard","Homogeneous structures yield CSP dichotomy: definable or hard"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The structures under consideration are model-complete cores and the new proof of the Larose-Tesson theorem for finite structures lifts directly to the infinite case without additional hidden assumptions on the reducts.","fun_headline_variants_meta":{"raw":{"variants":["CSPs over bounded homogeneous cores: FO or L-hard","First-order expansions split CSPs into AC0 or L-hard","Generalized Larose-Tesson: infinite CSPs FO or L-hard","Homogeneous structures yield CSP dichotomy: definable or hard"]},"model":"grok-4.3","cost_usd":0.00536,"raw_usage":{"total_tokens":2469,"prompt_tokens":596,"num_sources_used":0,"completion_tokens":69,"cost_in_usd_ticks":53603000,"prompt_tokens_details":{"text_tokens":596,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1804,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":596,"tokens_out":69,"duration_ms":14821,"temperature":1.0,"reasoning_tokens":1804,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-16T09:57:13.236447+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete first-order expansion of a finitely bounded homogeneous model-complete core whose CSP is solvable in deterministic logarithmic space yet not first-order definable would falsify the claimed dichotomy.","supporting_citations":[],"review_version":2}