5 papers
Dynamic 3-Coloring of Bipartite Graphs with Optimal Locality
Yann Bourreau, Filippo Casagrande, Tim Göttlicher +1
We give a dynamic graph algorithm which maintains a 3-coloring in bipartite graphs under edge insertions such that the coloring only changes within a radius of around a…
A Simple Construction of Locally Checkable Problems Filling the LOCAL Complexity Gaps in Graphs with Arbitrary Large Degrees
Filippo Casagrande, Pierre Fraigniaud, Benjamin Jauregui +1
We show that the complexity gaps in the round complexities of locally checkable labeling (LCL) problems are not due to the fact that solutions to LCL problems must be locally check…
New Hardness Results for the LOCAL Model via a Simple Self-Reduction
Alkida Balliu, Filippo Casagrande, Francesco d'Amore +1
Very recently, Khoury and Schild [FOCS 2025] showed that any randomized LOCAL algorithm that solves maximal matching requires rounds, where is the…
Orientation does not help with 3-coloring a grid in online-LOCAL
Thomas Boudier, Filippo Casagrande, Avinandan Das +4
The online-LOCAL and SLOCAL models are extensions of the LOCAL model where nodes are processed in a sequential but potentially adversarial order. So far, the only problem we know o…
Distributed Quantum Advantage in Locally Checkable Labeling Problems
Alkida Balliu, Filippo Casagrande, Francesco d'Amore +6
In this paper, we present the first known example of a locally checkable labeling problem (LCL) that admits asymptotic distributed quantum advantage in the LOCAL model of distribut…