Lorenzo Ciardo

STOC Conference 2024 Conference Paper

Semidefinite Programming and Linear Equations vs. Homomorphism Problems

• Lorenzo Ciardo
• Stanislav Zivný

SODA Conference 2023 Conference Paper

Approximate Graph Colouring and Crystals

• Lorenzo Ciardo
• Stanislav Zivný

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 exhibiting a graph fooling a level of the AIP hierarchy into the problem of constructing a highly symmetric crystal tensor. In order to prove the existence of crystals in arbitrary dimension, we provide a combinatorial characterisation for realisable systems of tensors; i. e. , sets of low-dimensional tensors that can be realised as the projections of a single high-dimensional tensor. * The research leading to these results has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reects only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein. This work was also supported by UKRI EP/X024431/1. † The full version of the paper can be accessed at https: //arxiv. org/abs/2210. 08293

STOC Conference 2023 Conference Paper

Approximate Graph Colouring and the Hollow Shadow

• Lorenzo Ciardo
• Stanislav Zivný

We show that approximate graph colouring is not solved by constantly many levels of the lift-and-project hierarchy for the combined basic linear programming and affine integer programming relaxation. The proof involves a construction of tensors whose fixed-dimensional projections are equal up to reflection and satisfy a sparsity condition, which may be of independent interest.

SODA Conference 2023 Conference Paper

Hierarchies of Minion Tests for PCSPs through Tensors

• Lorenzo Ciardo
• Stanislav Zivný

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 hierarchy into an algebraic part, depending on a minion capturing the “base level” of the hierarchy, and a geometric part - which we call tensorisation - inspired by multilinear algebra. We show that the hierarchies of minion tests obtained in this way are general enough to capture the (combinatorial) bounded width and also the Sherali-Adams LP, Sum-of-Squares SDP, and affine IP hierarchies. We exploit the geometry of the tensor spaces arising from our construction to prove general properties of such hierarchies. We identify certain classes of minions, which we call linear and conic, whose corresponding hierarchies have particularly fine features. Finally, in order to analyse the Sum-of-Squares SDP hierarchy we also characterise the solvability of the standard SDP relaxation through a new minion. * The research leading to these results has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein. This work was also supported by UKRI EP/X024431/1.

SODA Conference 2022 Conference Paper

CLAP: A New Algorithm for Promise CSPs

• Lorenzo Ciardo
• Stanislav Zivný

We propose a new algorithm for Promise Constraint Satisfaction Problems (PCSPs). It is a combination of the Constraint Basic LP relaxation and the Affine IP relaxation (CLAP). We give a characterisation of the power of CLAP in terms of a minion homomorphism. Using this characterisation, we identify a certain weak notion of symmetry which, if satisfied by infinitely many polymorphisms of PCSPs, guarantees tractability. We demonstrate that there are PCSPs solved by CLAP that are not solved by any of the existing algorithms for PCSPs; in particular, not by the BLP + AIP algorithm of Brakensiek and Guruswami [SODA'20] and not by a reduction to tractable finite-domain CSPs.