20 citations · 85 across the 19 of their papers we have counts for
9 papers · 1 filter
Algebraic and algorithmic synergies between promise and infinite-domain CSPs
Antoine Mottet
We establish a framework that allows us to transfer results between some constraint satisfaction problems with infinite templates and promise constraint satisfaction problems. On t…
Symmetries of structures that fail to interpret something finite
Libor Barto, Bertalan Bodor, Marcin Kozik +2
We investigate structural implications arising from the condition that a given directed graph does not interpret, in the sense of primitive positive interpretation with parameters…
An order out of nowhere: a new algorithm for infinite-domain CSPs
Antoine Mottet, Tomáš Nagy, Michael Pinsker
We consider the problem of satisfiability of sets of constraints in a given set of finite uniform hypergraphs. While the problem under consideration is similar in nature to the pro…
Collapsing the bounded width hierarchy for infinite-domain CSPs: when symmetries are enough
Antoine Mottet, Tomáš Nagy, Michael Pinsker +1
We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities ) have low relational width. This implies a c…
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…
Constraint Satisfaction Problems over Finite Structures
Libor Barto, William DeMeo, Antoine Mottet
We initiate a systematic study of the computational complexity of the Constraint Satisfaction Problem (CSP) over finite structures that may contain both relations and operations. W…
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…