2 papers
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.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…