4 citations · 4 across the 2 of their papers we have counts for
4 papers · 1 filter
Smooth approximations and CSPs over finitely bounded homogeneous structures
Antoine Mottet, Michael Pinsker
We develop the novel machinery of smooth approximations, and apply it to confirm the CSP dichotomy conjecture for first-order reducts of the random tournament, various homogeneous…
When symmetries are not enough: a hierarchy of hard Constraint Satisfaction Problems
Pierre Gillibert, Julius Jonušas, Michael Kompatscher +2
We produce a class of -categorical structures with finite signature by applying a model-theoretic construction -- a refinement of the Hrushosvki-encoding -- to -categorical s…
Topology is relevant (in a dichotomy conjecture for infinite-domain constraint satisfaction problems)
Manuel Bodirsky, Antoine Mottet, Miroslav Olšák +3
The algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial…
Classification transfer for qualitative reasoning problems
Barnaby Martin, Peter Jonsson, Manuel Bodirsky +1
We study formalisms for temporal and spatial reasoning in the modern context of Constraint Satisfaction Problems (CSPs). We show how questions on the complexity of their subclasses…