47 citations · 48 across the 2 of their papers we have counts for
6 papers
Fast Distributed Brooks' Theorem
Manuela Fischer, Yannic Maus, Magnús M. Halldórsson
We give a randomized -coloring algorithm in the LOCAL model that runs in rounds, where is the number of nodes of the input graph and is its max…
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…
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…
A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics
Manuela Fischer, Mohsen Ghaffari
\emph{Sampling} constitutes an important tool in a variety of areas: from machine learning and combinatorial optimization to computational physics and biology. A central class of s…
Sublogarithmic Distributed Algorithms for Lovász Local lemma, and the Complexity Hierarchy
Manuela Fischer, Mohsen Ghaffari
Locally Checkable Labeling (LCL) problems include essentially all the classic problems of distributed algorithms. In a recent enlightening revelation, Chang and Pe…