3 papers
quant-ph2026
Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction
Lorenzo Ciardo, Gideo Joubert, Antoine Mottet
We introduce the concept of quantum polymorphisms to the complexity theory of quantum constraint satisfaction. Via this notion, we build an algebraic framework of reductions betwee…
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…