17 citations · 21 across the 10 of their papers we have counts for
8 papers · 1 filter
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…
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…
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…
Approximate Graph Colouring and Crystals
Lorenzo Ciardo, Stanislav Živný
We show that approximate graph colouring is not solved by any level of the affine integer programming (AIP) hierarchy. To establish the result, we translate the problem of exhibiti…
Hierarchies of Minion Tests for PCSPs through Tensors
Lorenzo Ciardo, 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…
The Sherali-Adams Hierarchy for Promise CSPs through Tensors
Lorenzo Ciardo, Stanislav Živný
We study the Sherali-Adams linear programming hierarchy in the context of promise constraint satisfaction problems (PCSPs). We characterise when a level of the hierarchy accepts an…
CLAP: A New Algorithm for Promise CSPs
Lorenzo Ciardo, Stanislav Živný
We propose a new algorithm for Promise Constraint Satisfaction Problems PCSPs). It is a combination of the onstraint Basic P relaxation and the …