26 citations · 100 across the 29 of their papers we have counts for
5 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…
Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model
Sebastian Brandt, Manuela Fischer, Jara Uitto
The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale parallel computation frameworks and has recently gained a lot of importance…
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…
Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory
Sebastian Brandt, Manuela Fischer, Jara Uitto
Recently, studying fundamental graph problems in the \emph{Massively Parallel Computation (MPC) framework, inspired by the MapReduce paradigm, has gained a lot of attention. An ass…
Distributed Recoloring
Marthe Bonamy, Paul Ouvrard, Mikaël Rabie +2
Given two colorings of a graph, we consider the following problem: can we recolor the graph from one coloring to the other through a series of elementary changes, such that the gra…