1 citations · 1 across the 5 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
cs.DS2023
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…
cs.DC2023★ 1 cited
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…