6 citations · 27 across the 32 of their papers we have counts for
7 papers · 1 filter
Efficient Deterministic Distributed Coloring with Small Bandwidth
Philipp Bamberger, Fabian Kuhn, Yannic Maus
We show that the -list coloring problem can be solved deterministically in rounds in the \CONGEST model, where is the diameter of t…
Classification of distributed binary labeling problems
Alkida Balliu, Sebastian Brandt, Yuval Efron +4
We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable…
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…
P-SLOCAL-Completeness of Maximum Independent Set Approximation
Yannic Maus
We prove that the maximum independent set approximation problem with polylogarithmic approximation factor is P-SLOCAL-complete. Thus an efficient algorithm for the maximum independ…
On the Complexity of Distributed Splitting Problems
Philipp Bamberger, Mohsen Ghaffari, Fabian Kuhn +2
One of the fundamental open problems in the area of distributed graph algorithms is the question of whether randomization is needed for efficient symmetry breaking. While there are…
Deterministic Distributed Dominating Set Approximation in the CONGEST Model
Janosch Deurer, Fabian Kuhn, Yannic Maus
We develop deterministic approximation algorithms for the minimum dominating set problem in the CONGEST model with an almost optimal approximation guarantee. For $ε>1/{\text{poly}}…