2 papers
cs.LO2025
When Darwin met Ianus: dichotomies of expressivity
Johanna Brunar, Michael Pinsker, Moritz Schöbi
The classifications of temporal and phylogeny constraint languages stand among the most seminal complexity classifications within infinite-domain Constraint Satisfaction Problems (…
cs.LO2025
The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems
Johanna Brunar, Marcin Kozik, Tomáš Nagy +1
Two major milestones on the road to the full complexity dichotomy for finite-domain constraint satisfaction problems were Bulatov's proof of the dichotomy for conservative template…