5 citations · 7 across the 9 of their papers we have counts for
19 papers · 1 filter
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…
Distributed Edge Coloring in Time Polylogarithmic in
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +1
We provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main resu…
Efficient Classification of Locally Checkable Problems in Regular Trees
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang +3
We give practical, efficient algorithms that automatically determine the asymptotic distributed round complexity of a given locally checkable graph problem in the $[Θ(\log n), Θ(n)…
Towards a Complexity Classification of LCL Problems in Massively Parallel Computation
Sebastian Brandt, Rustam Latypov, Jara Uitto
In this work, we develop the low-space Massively Parallel Computation (MPC) complexity landscape for a family of fundamental graph problems on trees. We present a general method th…
Distributed -Coloring Plays Hide-and-Seek
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +1
We prove several new tight distributed lower bounds for classic symmetry breaking graph problems. As a basic tool, we first provide a new insightful proof that any deterministic di…
Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +1
Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first lower bound for the maximal independent set (MIS) problem in trees. In this work we prove lower bou…