20 citations · 85 across the 19 of their papers we have counts for
23 papers
Schrijver-Delsarte rigidity in association schemes and undecidability of quantum graph homomorphism
Lorenzo Ciardo, Iris Hebbeker, Gideo Joubert +2
We prove RE-completeness of the quantum homomorphism problem parameterised by families of graphs derived from the classic metric association schemes. These include Kneser graphs, $…
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…
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…
Finite Algebras with Hom-Sets of Polynomial Size
Libor Barto, Antoine Mottet
We provide an internal characterization of those finite algebras (i.e., algebraic structures) such that the number of homomorphisms from any finite algebra …
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…