47 citations · 79 across the 10 of their papers we have counts for
14 papers
Deterministic Massively Parallel Symmetry Breaking for Sparse Graphs
Manuela Fischer, Jeff Giliberti, Christoph Grunau
We consider the problem of designing deterministic graph algorithms for the model of Massively Parallel Computation (MPC) that improve with the sparsity of the input graph, as meas…
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…
Exponential Speedup Over Locality in MPC with Optimal Memory
Alkida Balliu, Sebastian Brandt, Manuela Fischer +4
Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example p…
Improved Deterministic Connectivity in Massively Parallel Computation
Manuela Fischer, Jeff Giliberti, Christoph Grunau
A long line of research about connectivity in the Massively Parallel Computation model has culminated in the seminal works of Andoni et al. [FOCS'18] and Behnezhad et al. [FOCS'19]…
Deterministic -Approximate Maximum Matching with Passes in the Semi-Streaming Model and Beyond
Manuela Fischer, Slobodan Mitrović, Jara Uitto
We present a deterministic -approximate maximum matching algorithm in passes in the semi-streaming model, solving the long-standing o…
Triangle resilience of the square of a Hamilton cycle in random graphs
Manuela Fischer, Nemanja Škorić, Angelika Steger +1
Since first introduced by Sudakov and Vu in 2008, the study of resilience problems in random graphs received a lot of attention in probabilistic combinatorics. Of particular intere…
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…
Tight Analysis of Randomized Greedy MIS
Manuela Fischer, Andreas Noever
We provide a tight analysis which settles the round complexity of the well-studied parallel randomized greedy MIS algorithm, thus answering the main open question of Blelloch, Fine…
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…
Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching
Manuela Fischer, Mohsen Ghaffari, Fabian Kuhn
We present a deterministic distributed algorithm that computes a -edge-coloring, or even list-edge-coloring, in any -node graph with maximum degree , in $O(\log^7 Δ\l…
Improved Deterministic Distributed Matching via Rounding
Manuela Fischer
We present improved deterministic distributed algorithms for a number of well-studied matching problems, which are simpler, faster, more accurate, and/or more general than their kn…