14 citations · 38 across the 19 of their papers we have counts for
30 papers
On the Node-Averaged Complexity of Locally Checkable Problems on Trees
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +2
Over the past decade, a long line of research has investigated the distributed complexity landscape of locally checkable labeling (LCL) problems on bounded-degree graphs, culminati…
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
Alkida Balliu, Sebastian Brandt, Fabian Kuhn +1
We investigate the distributed complexity of maximal matching and maximal independent set (MIS) in hypergraphs in the LOCAL model. A maximal matching of a hypergraph …
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)…
The Landscape of Distributed Complexities on Trees and Beyond
Christoph Grunau, Vaclav Rozhon, Sebastian Brandt
We study the local complexity landscape of locally checkable labeling (LCL) problems on constant-degree graphs with a focus on complexities below . Our contribution is th…
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…
On Homomorphism Graphs
Sebastian Brandt, Yi-Jun Chang, Jan Grebík +3
We introduce a new type of examples of bounded degree acyclic Borel graphs and study their combinatorial properties in the context of descriptive combinatorics, using a generalizat…
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…
The randomized local computation complexity of the Lovász local lemma
Sebastian Brandt, Christoph Grunau, Václav Rozhoň
The Local Computation Algorithm (LCA) model is a popular model in the field of sublinear-time algorithms that measures the complexity of an algorithm by the number of probes the al…
Locally Checkable Problems in Rooted Trees
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang +4
Consider any locally checkable labeling problem in rooted regular trees: there is a finite set of labels , and for each label we specify what are permitted label c…
Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
Sebastian Brandt, Christoph Grunau, Václav Rozhoň
Recently, Brandt, Maus and Uitto [PODC'19] showed that, in a restricted setting, the dependency of the complexity of the distributed Lovász Local Lemma (LLL) on the chosen LLL crit…
Tight Bounds for Deterministic High-Dimensional Grid Exploration
Sebastian Brandt, Julian Portmann, Jara Uitto
We study the problem of exploring an oriented grid with autonomous agents governed by finite automata. In the case of a 2-dimensional grid, the question how many agents are require…
Efficient Load-Balancing through Distributed Token Dropping
Sebastian Brandt, Barbara Keller, Joel Rybicki +2
We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an e…
Distributed Lower Bounds for Ruling Sets
Alkida Balliu, Sebastian Brandt, Dennis Olivetti
Given a graph , an -ruling set is a subset such that the distance between any two vertices in is at least , and the distance between any v…
Truly Tight-in- Bounds for Bipartite Maximal Matching and Variants
Sebastian Brandt, Dennis Olivetti
In a recent breakthrough result, Balliu et al. [FOCS'19] proved a deterministic -round and a randomized -ro…
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…
Online Graph Exploration on a Restricted Graph Class: Optimal Solutions for Tadpole Graphs
Sebastian Brandt, Klaus-Tycho Foerster, Jonathan Maurer +1
We study the problem of online graph exploration on undirected graphs, where a searcher has to visit every vertex and return to the origin. Once a new vertex is visited, the search…
An Automatic Speedup Theorem for Distributed Problems
Sebastian Brandt
Recently, Brandt et al. [STOC'16] proved a lower bound for the distributed Lovász Local Lemma, which has been conjectured to be tight for sufficiently relaxed LLL criteria by Chang…
How much does randomness help with locally checkable problems?
Alkida Balliu, Sebastian Brandt, Dennis Olivetti +1
Locally checkable labeling problems (LCLs) are distributed graph problems in which a solution is globally feasible if it is locally feasible in all constant-radius neighborhoods. V…
Lower bounds for maximal matchings and maximal independent sets
Alkida Balliu, Sebastian Brandt, Juho Hirvonen +3
There are distributed graph algorithms for finding maximal matchings and maximal independent sets in communication rounds; here is the number of nodes and …
The distributed complexity of locally checkable problems on paths is decidable
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang +3
Consider a computer network that consists of a path with nodes. The nodes are labeled with inputs from a constant-sized set, and the task is to find output labels from a consta…