47 citations · 79 across the 10 of their papers we have counts for
4 papers · 1 filter
Tight Analysis of Randomized Greedy MIS
Manuela Fischer, Andreas Noever
We provide a tight analysis which settles the round complexity of the well-studied parallel randomized greedy MIS algorithm, thus answering the main open question of Blelloch, Fine…
Sublogarithmic Distributed Algorithms for Lovász Local lemma, and the Complexity Hierarchy
Manuela Fischer, Mohsen Ghaffari
Locally Checkable Labeling (LCL) problems include essentially all the classic problems of distributed algorithms. In a recent enlightening revelation, Chang and Pe…
Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
Manuela Fischer, Mohsen Ghaffari, Fabian Kuhn
We present a deterministic distributed algorithm that computes a -edge-coloring, or even list-edge-coloring, in any -node graph with maximum degree , in $O(\log^7 Δ\l…
Improved Deterministic Distributed Matching via Rounding
Manuela Fischer
We present improved deterministic distributed algorithms for a number of well-studied matching problems, which are simpler, faster, more accurate, and/or more general than their kn…