REVIEW 1 major objections 1 minor
Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
T0 review · 1 major / 1 minor · reviewed 2026-05-16 · grok-4.3
Pith's one-line read CSPs over first-order expansions of finitely bounded homogeneous model-complete cores are either first-order definable or L-hard under first-order reduction.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (1)
- [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.
minor comments (1)
- [Introduction] 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.
Simulated Author's Rebuttal
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.
read point-by-point responses
-
Referee: [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.
Authors: 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: yes
Circularity Check
No circularity: new finite proof is independent and generalization uses it as base without reduction to inputs
full rationale
The paper explicitly states it first derives a new proof of the Larose-Tesson theorem for finite structures and only then generalizes that proof to the infinite case of first-order expansions of finitely bounded homogeneous model-complete cores. No quoted step equates a prediction or central claim to a fitted parameter, self-citation chain, or definitional renaming; the finite-case proof is presented as freshly constructed rather than presupposing the infinite result. The derivation chain therefore remains self-contained against external benchmarks.
Assumptions & free parameters
assumptions (1)
- standard math Standard background results from model theory (homogeneous structures, model-complete cores) and complexity theory (first-order reductions, AC0, L).
Cite this review
Pith. "Pith review of Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard." pith.science (2026). https://pith.science/paper/OKOX6BGZ
@misc{pith2026260122691,
author = {Pith},
title = {Pith review of: Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard},
year = {2026},
howpublished = {\url{https://pith.science/paper/OKOX6BGZ}},
note = {Machine review of arXiv:2601.22691}
}
abstract
Feder-Vardi conjecture, which proposed that every finite-domain Constraint Satisfaction Problem (CSP) is either in P or it is NP-complete, has been solved independently by Bulatov and Zhuk almost ten years ago. Bodirsky-Pinsker conjecture which states a similar dichotomy for countably infinite first-order reducts of finitely bounded homogeneous structures is wide open. In this paper, we prove that CSPs over first-order expansions of finitely bounded homogeneous model-complete cores are either first-order definable (and hence in non-uniform AC$^0$) or L-hard under first-order reduction. It is arguably the most general complexity dichotomy when it comes to the scope of structures within Bodirsky-Pinsker conjecture. Our strategy is that we first give a new proof of Larose-Tesson theorem, which provides a similar dichotomy over finite structures, and then generalize that new proof to infinite structures.
Reviewed May 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.