
Improved Distributed Lower Bounds for MIS and Bounded (Out)Degree Dominating Sets in Trees
Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first ω(log...
read it

Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
We study connections between distributed local algorithms, finitary fact...
read it

The randomized local computation complexity of the Lovász local lemma
The Local Computation Algorithm (LCA) model is a popular model in the fi...
read it

Locally Checkable Problems in Rooted Trees
Consider any locally checkable labeling problem Π in rooted regular tree...
read it

Generalizing the Sharp Threshold Phenomenon for the Distributed Complexity of the Lovász Local Lemma
Recently, Brandt, Maus and Uitto [PODC'19] showed that, in a restricted ...
read it

Tight Bounds for Deterministic HighDimensional Grid Exploration
We study the problem of exploring an oriented grid with autonomous agent...
read it

Efficient LoadBalancing through Distributed Token Dropping
We introduce a new graph problem, the token dropping game, and we show h...
read it

Distributed Lower Bounds for Ruling Sets
Given a graph G = (V,E), an (α, β)ruling set is a subset S ⊆ V such tha...
read it

Truly TightinΔ Bounds for Bipartite Maximal Matching and Variants
In a recent breakthrough result, Balliu et al. [FOCS'19] proved a determ...
read it

Classification of distributed binary labeling problems
We present a complete classification of the deterministic distributed ti...
read it

Online Graph Exploration on a Restricted Graph Class: Optimal Solutions for Tadpole Graphs
We study the problem of online graph exploration on undirected graphs, w...
read it

An Automatic Speedup Theorem for Distributed Problems
Recently, Brandt et al. [STOC'16] proved a lower bound for the distribut...
read it

How much does randomness help with locally checkable problems?
Locally checkable labeling problems (LCLs) are distributed graph problem...
read it

Lower bounds for maximal matchings and maximal independent sets
There are distributed graph algorithms for finding maximal matchings and...
read it

The distributed complexity of locally checkable problems on paths is decidable
Consider a computer network that consists of a path with n nodes. The no...
read it

Matching and MIS for Uniformly Sparse Graphs in the LowMemory MPC Model
The Massively Parallel Computation (MPC) model serves as a common abstra...
read it

Almost Global Problems in the LOCAL Model
The landscape of the distributed time complexity is nowadays wellunders...
read it

Towards Analytics Aware Ontology Based Access to Static and Streaming Data (Extended Version)
Realtime analytics that requires integration and aggregation of heterog...
read it
Sebastian Brandt
is this you? claim profile