47 citations · 207 across the 54 of their papers we have counts for
71 papers
LOCAL LLL in Rounds
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson +2
We provide a -round randomized LOCAL algorithm for the constructive Lovász Local Lemma with polynomial criterion , for a sufficiently l…
Robust Shattering Arguments
Mohsen Ghaffari, Magnús M. Halldórsson, Yannic Maus +1
Graph shattering is a central technique underlying sublogarithmic-time distributed algorithms in the LOCAL model. Its analysis typically relies on bounding the probability that lar…
Distributed MIS with Low Energy and Time Complexities
Mohsen Ghaffari, Julian Portmann
We present randomized distributed algorithms for the maximal independent set problem (MIS) that, while keeping the time complexity nearly matching the best known, reduce the energy…
A Near-Optimal Deterministic Distributed Synchronizer
Mohsen Ghaffari, Anton Trygub
We provide the first deterministic distributed synchronizer with near-optimal time complexity and message complexity overheads. Concretely, given any distributed algorithm $\mathca…
Average Awake Complexity of MIS and Matching
Mohsen Ghaffari, Julian Portmann
Chatterjee, Gmyr, and Pandurangan [PODC 2020] recently introduced the notion of awake complexity for distributed algorithms, which measures the number of rounds in which a node is…
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…