6 papers
Hierarchies of Minion Tests for PCSPs through Tensors
Lorenzo Ciardo, Stanislav Živný, Stanislav Živný
We provide a unified framework to study hierarchies of relaxations for Constraint Satisfaction Problems and their Promise variant. The idea is to split the description of a hierarc…
Approximate Graph Colouring and the Crystal with a Hollow Shadow
Lorenzo Ciardo, Stanislav Živný
We show that approximate graph colouring is not solved by the lift-and-project hierarchy for the combination of linear programming and linear Diophantine equations. The proof is ba…
1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
Lorenzo Ciardo, Marcin Kozik, Andrei Krokhin +2
The 1-in-3 and Not-All-Equal satisfiability problems for Boolean CNF formulas are two well-known NP-hard problems. In contrast, the promise 1-in-3 vs. Not-All-Equal problem can be…
The periodic structure of local consistency
Lorenzo Ciardo, Stanislav Živný
We connect the mixing behaviour of random walks over a graph to the power of the local-consistency algorithm for the solution of the corresponding constraint satisfaction problem (…
Semidefinite programming and linear equations vs. homomorphism problems
Lorenzo Ciardo, Stanislav Živný
We introduce a relaxation for homomorphism problems that combines semidefinite programming with linear Diophantine equations, and propose a framework for the analysis of its power…
Quantum Advantage and CSP Complexity
Lorenzo Ciardo
Information-processing tasks modelled by homomorphisms between relational structures can witness quantum advantage when entanglement is used as a computational resource. We prove t…