92 citations · 480 across the 54 of their papers we have counts for
5 papers · 1 filter
Distributed Binary Labeling Problems in High-Degree Graphs
Henrik Lievonen, Timothé Picavet, Jukka Suomela
Balliu et al. (DISC 2020) classified the hardness of solving binary labeling problems with distributed graph algorithms; in these problems the task is to select a subset of edges i…
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…
Distributed derandomization revisited
Sameep Dahal, Francesco d'Amore, Henrik Lievonen +2
One of the cornerstones of the distributed complexity theory is the derandomization result by Chang, Kopelowitz, and Pettie [FOCS 2016]: any randomized LOCAL algorithm that solves…
Fast Dynamic Programming in Trees in the MPC Model
Chetan Gupta, Rustam Latypov, Yannic Maus +6
We present a deterministic algorithm for solving a wide range of dynamic programming problems in trees in rounds in the massively parallel computation model (MPC), with…
Distributed Half-Integral Matching and Beyond
Sameep Dahal, Jukka Suomela
By prior work, it is known that any distributed graph algorithm that finds a maximal matching requires communication rounds, while it is possible to find a maximal fr…