17 citations · 21 across the 10 of their papers we have counts for
13 papers
The Kemeny-Braess Paradox in Random Graphs
Manuel Bodirsky, Lorenzo Ciardo, Mihyun Kang
In 2016, Kirkland and Zeng initiated the mathematical treatment of Braess paradox for random walks on graphs using Kemeny's constant as the measure of travel time. We study this ph…
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 (…
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…
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 …
Perron value and moment of rooted trees
Lorenzo Ciardo
The Perron value of a rooted tree has a central role in the study of the algebraic connectivity and characteristic set, and it can be considered a weight of spectral nat…
On Kemeny's constant for trees with fixed order and diameter
Lorenzo Ciardo, Geir Dahl, Steve Kirkland
Kemeny's constant of a connected graph is a measure of the expected transit time for the random walk associated with . In the current work, we consider the case when…
The Braess' Paradox for Pendant Twins
Lorenzo Ciardo
The Kemeny's constant of a connected undirected graph can be interpreted as the expected transit time between two randomly chosen vertices for the Markov chain associate…