b'Yannic Maus'

research

∙ 08/01/2023

Conditionally Optimal Parallel Coloring of Forests

We show the first conditionally optimal deterministic algorithm for 3-co...

0 Christoph Grunau, et al. ∙

research

∙ 05/05/2023

Fast Dynamic Programming in Trees in the MPC Model

We present a deterministic algorithm for solving a wide range of dynamic...

0 Chetan Gupta, et al. ∙

research

∙ 03/13/2023

Drawings of Complete Multipartite Graphs Up to Triangle Flips

For a drawing of a labeled graph, the rotation of a vertex or crossing i...

0 Oswin Aichholzer, et al. ∙

research

∙ 02/14/2023

Distributed Symmetry Breaking on Power Graphs via Sparsification

In this paper, we present efficient distributed algorithms for classical...

0 Yannic Maus, et al. ∙

research

∙ 02/08/2023

Adaptive Massively Parallel Connectivity in Optimal Space

We study the problem of finding connected components in the Adaptive Mas...

0 Jakub Łącki, et al. ∙

research

∙ 11/14/2022

Fast Distributed Brooks' Theorem

We give a randomized Δ-coloring algorithm in the LOCAL model that runs i...

0 Manuela Fischer, et al. ∙

research

∙ 11/07/2022

Optimal Deterministic Massively Parallel Connectivity on Forests

We show fast deterministic algorithms for fundamental problems on forest...

0 Alkida Balliu, et al. ∙

research

∙ 08/19/2022

Exponential Speedup Over Locality in MPC with Optimal Memory

Locally Checkable Labeling (LCL) problems are graph problems in which a ...

0 Alkida Balliu, et al. ∙

research

∙ 08/17/2022

Fast Distributed Vertex Splitting with Applications

We present polyloglog n-round randomized distributed algorithms to compu...

0 Magnus M. Halldorsson, et al. ∙

research

∙ 09/14/2021

Distributed Vertex Cover Reconfiguration

Reconfiguration schedules, i.e., sequences that gradually transform one ...

0 Keren Censor-Hillel, et al. ∙

research

∙ 08/05/2021

Efficient CONGEST Algorithms for the Lovasz Local Lemma

We present a poly loglog n time randomized CONGEST algorithm for a natur...

0 Yannic Maus, et al. ∙

research

∙ 05/12/2021

Distributed Graph Coloring Made Easy

In this paper we present a deterministic CONGEST algorithm to compute an...

0 Yannic Maus, et al. ∙

research

∙ 05/12/2021

Locally Checkable Labelings with Small Messages

A rich line of work has been addressing the computational complexity of ...

0 Alkida Balliu, et al. ∙

research

∙ 02/14/2021

Near-Optimal Scheduling in the Congested Clique

This paper provides three nearly-optimal algorithms for scheduling t job...

0 Keren Censor-Hillel, et al. ∙

research

∙ 12/28/2020

Efficient Randomized Distributed Coloring in CONGEST

Distributed vertex coloring is one of the classic problems and probably ...

0 Magnus M. Halldorsson, et al. ∙

research

∙ 08/10/2020

Coloring Fast Without Learning Your Neighbors' Colors

We give an improved randomized CONGEST algorithm for distance-2 coloring...

0 Magnus M. Halldorsson, et al. ∙

research

∙ 07/30/2020

Local Conflict Coloring Revisited: Linial for Lists

Linial's famous color reduction algorithm reduces a given m-coloring of ...

0 Yannic Maus, et al. ∙

research

∙ 06/06/2020

Distributed Approximation on Power Graphs

We investigate graph problems in the following setting: we are given a g...

0 Reuven Bar-Yehuda, et al. ∙

research

∙ 05/13/2020

Distance-2 Coloring in the CONGEST Model

We give efficient randomized and deterministic distributed algorithms fo...

0 Magnus M. Halldorsson, et al. ∙

research

∙ 12/05/2019

Efficient Deterministic Distributed Coloring with Small Bandwidth

We show that the (degree+1)-list coloring problem can be solved determin...

0 Philipp Bamberger, et al. ∙

research

∙ 11/29/2019

Classification of distributed binary labeling problems

We present a complete classification of the deterministic distributed ti...

0 Alkida Balliu, et al. ∙

research

∙ 08/17/2019

A Sharp Threshold Phenomenon for the Distributed Complexity of the Lovasz Local Lemma

The Lovász Local Lemma (LLL) says that, given a set of bad events that d...

0 Sebastian Brand, et al. ∙

research

∙ 07/24/2019

P-SLOCAL-Completeness of Maximum Independent Set Approximation

We prove that the maximum independent set approximation problem with pol...

0 Yannic Maus, et al. ∙

research

∙ 05/28/2019

On the Complexity of Distributed Splitting Problems

One of the fundamental open problems in the area of distributed graph al...

0 Philipp Bamberger, et al. ∙

research

∙ 05/26/2019

Deterministic Distributed Dominating Set Approximation in the CONGEST Model

We develop deterministic approximation algorithms for the minimum domina...

0 Janosch Deurer, et al. ∙

research

∙ 04/24/2019

Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol

We study a process of averaging in a distributed system with noisy commu...

0 Frederik Mallmann-Trenn, et al. ∙

research

∙ 05/18/2018

Deterministic Distributed Ruling Sets of Line Graphs

An (α,β)-ruling set of a graph G=(V,E) is a set R⊆ V such that for any n...

0 Fabian Kuhn, et al. ∙

research

∙ 03/08/2018

Improved Distributed Δ-Coloring

We present a randomized distributed algorithm that computes a Δ-coloring...

0 Mohsen Ghaffari, et al. ∙

research

∙ 02/27/2018

Local Distributed Algorithms in Highly Dynamic Networks

The present paper studies local distributed graph problems in highly dyn...

0 Philipp Bamberger, et al. ∙

research

∙ 11/15/2017

Deterministic Distributed Edge-Coloring with Fewer Colors

We present a deterministic distributed algorithm, in the LOCAL model, th...

0 Mohsen Ghaffari, et al. ∙

Yannic Maus

Featured Co-authors