47 citations · 104 across the 24 of their papers we have counts for
32 papers · 1 filter
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…
Nearly Work-Efficient Parallel DFS in Undirected Graphs
Mohsen Ghaffari, Christoph Grunau, Jiahao Qu
We present the first parallel depth-first search algorithm for undirected graphs that has near-linear work and sublinear depth. Concretely, in any -node -edge undirected grap…
Faster Deterministic Distributed MIS and Approximate Matching
Mohsen Ghaffari, Christoph Grunau
We present an round deterministic distributed algorithm for the maximal independent set problem. By known reductions, thi…