Showing cs.LOShow all
3 papers · 1 filter
cs.LO2025
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…
cs.LO2025
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…
cs.LO2024
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…