11 citations · 16 across the 4 of their papers we have counts for
6 papers · 1 filter
A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
Sebastian Brandt, Yannic Maus, Jara Uitto
The Lovász Local Lemma (LLL) says that, given a set of bad events that depend on the values of some random variables and where each event happens with probability at most and d…
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…
Deterministic Distributed Edge-Coloring with Fewer Colors
Mohsen Ghaffari, Fabian Kuhn, Yannic Maus +1
We present a deterministic distributed algorithm, in the LOCAL model, that computes a -edge-coloring in polylogarithmic-time, so long as the maximum degree $Δ=\tildeΩ(\l…