47 citations · 207 across the 54 of their papers we have counts for
7 papers · 1 filter
The Complexity of Coloring inCongested Clique, Massively Parallel Computation,and Centralized Local Computation
Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari +2
We present new randomized algorithms that improve the complexity of the classic -coloring problem, and its generalization -list-coloring, in three well-studied models…
Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
Mohsen Ghaffari, Jara Uitto
We introduce a method for sparsifying distributed algorithms and exhibit how it leads to improvements that go past known barriers in two algorithmic settings of large-scale graph p…
New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms
Mohsen Ghaffari, Jason Li
We show that many classical optimization problems --- such as -approximate maximum flow, shortest path, and transshipment --- can be computed in $\newcommand{\tmix}{τ_{\te…
Distributed Computation in Node-Capacitated Networks
John Augustine, Mohsen Ghaffari, Robert Gmyr +4
In this paper, we study distributed graph algorithms in networks in which the nodes have a limited communication capacity. Many distributed systems are built on top of an underlyin…
Improved Distributed -Coloring
Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn +1
We present a randomized distributed algorithm that computes a -coloring in any non-complete graph with maximum degree in rounds,…
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
Mohsen Ghaffari, Themis Gouleakis, Christian Konrad +2
We present -round algorithms in the Massively Parallel Computation (MPC) model, with memory per machine, that compute a maximal independent set, a $1+…