2 citations · 4 across the 9 of their papers we have counts for
4 papers · 1 filter
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…