38 citations · 178 across the 46 of their papers we have counts for
69 papers
On the Node-Averaged Complexity of Locally Checkable Problems on Trees
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +2
Over the past decade, a long line of research has investigated the distributed complexity landscape of locally checkable labeling (LCL) problems on bounded-degree graphs, culminati…
No distributed quantum advantage for approximate graph coloring
Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala +7
We give an almost complete characterization of the hardness of -coloring -chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. I…
Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem
Mélanie Cambus, Fabian Kuhn, Shreyas Pai +1
In this work, we present a constant-round algorithm for the -ruling set problem in the Congested Clique model. As a direct consequence, we obtain a constant round algorithm in t…
Coloring Fast with Broadcasts
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson +2
We present an -round distributed algorithm for the -coloring problem, where each node broadcasts only one -bit message per round to its neighbors…
List Defective Colorings: Distributed Algorithms and Applications
Marc Fuchs, Fabian Kuhn
The distributed coloring problem is at the core of the area of distributed graph algorithms and it is a problem that has seen tremendous progress over the last few years. Much of t…
A Distributed Palette Sparsification Theorem
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson +2
The celebrated palette sparsification result of [Assadi, Chen, and Khanna SODA'19] shows that to compute a coloring of the graph, where denotes the maximum degree, it suf…